Introduc)on
Data
Compression
DATA
COMPRESSION
DATA
COMPRESSION:
REMOVE
REDUNDANCY
DATA
COMPRESSION
DATA
COMPRESSION:
REMOVE
REDUNDANCY
DATA
COMPRESSION
STORAGE
-‐-‐-‐-‐-‐-‐-‐-‐
FAST
TRANSMISSION
DATA
COMPRESSION
DATA
COMPRESSION
compression
ra)o
=
B0/B1
B0
=
number
of
bits
before
compression
B1
=
number
of
bits
aCer
compression
DATA
COMPRESSION
We
desire
that
X
and
Y
be
as
similar
as
possible
Smaller
space…
compression
ra)o
=
B0/B1
B0
=
number
of
bits
before
compression
B1
=
number
of
bits
aCer
compression
Just
to
understand
(some
examples
that
you
already
know):
!
quan9za9on:
lossy
compression
!
Fourier
sub-‐sampling
sa9sfying
Nyquist:
lossless
compression
!
Fourier
sub-‐sampling
which
does
not
sa9sfy
Nyquist:
lossy
compression
these
are
also
considered
compression
techniques,
and
oCen
are
used
jointly
with
other
compression
methods.
Just
to
understand
(some
examples
that
you
already
know):
!
modeling:
lossy
compression
(regression),
lossless
compression
(interpola)on)
these
are
also
considered
compression
techniques,
and
oCen
are
used
jointly
with
other
compression
methods.
regression
interpola)on
Just
to
understand
(some
examples
that
you
already
know):
!
predic9on:
(related
to
modeling)
these
are
also
considered
compression
techniques,
and
oCen
are
used
jointly
with
other
compression
methods.
Just
to
understand
(some
examples
that
you
already
know):
!
quan9za9on:
lossy
compression
(already
men)oned
in
other
slide)
!
clustering
or
smoothing:
lossy
compression
these
are
also
considered
compression
techniques,
and
oCen
are
used
jointly
with
other
compression
methods.
Especially
for
clustering,
please
think
in
removing
redundancy
quan)za)on
clustering
Sta9s9cal
redudancy
Lossless and Lossy Compression Techniques
• Data compression techniques are broadly classified into
lossless and lossy.
• Lossless techniques enable exact reconstruction of the
original document from the compressed information.
• Exploit redundancy in data
• Applied to general data
• Examples: Run-length, Huffman, LZ77, LZ78, and LZW
• Lossy compression - reduces a file by permanently
eliminating certain redundant information
• Exploit redundancy and human perception
• Applied to audio, image, and video
• Examples: JPEG and MPEG
• Lossy techniques usually achieve higher compression rates
than lossless ones but the latter are more accurate.
Compression Utilities and Formats
• Compression tool examples:
• winzip, pkzip, compress, gzip
• General compression formats:
• .zip, .gz
• Common image compression formats:
JPEG, JPEG 2000, BMP, GIF, PCX, PNG, TGA, TIFF, WMP
• Common audio (sound) compression formats:
MPEG-1 Layer III (known as MP3), RealAudio (RA, RAM, RP), AU, Vorbis, WMA, AIFF,
WAVE, G.729a
• Common video (sound and image) compression formats:
MPEG-1, MPEG-2, MPEG-4, DivX, Quicktime (MOV), RealVideo (RM), Windows Media
Video (WMV), Video for Windows (AVI), Flash video (FLV)