DIP2
Data Compression Techniques
Data Compression -Introduction
• Data compression is the art or science of representing
information in a compact form.
• We create these compact representations by
identifying and using structures that exist in the data.
• Data can be characters in a text file, numbers that are
samples of speech or image waveforms, or sequences
of numbers that are generated by other processes.
Data compression cont…
• The reason we need data compression is that more and
more of the information that we generate and use is in
digital form—consisting of numbers represented by bytes of
data.
• And the number of bytes required to represent
multimedia data can be huge.
• For example, in order to digitally represent 1 second of
video without compression (using the CCIR 601 format), we
need more than 20 megabytes, or 160 megabits
Data compression..
• To represent 2 minutes of uncompressed CD-quality music
(44,100 samples per second, 16 bits per sample) requires
more than 84 million bits.
• Downloading music from a website at these rates would
take a long time.
• Data compression can be viewed as a means for efficient
representation of a digital source of data such as text,
image, sound or any combination of all these types such
as video.
Data compression…
• The goal of data compression is to represent a source in
digital form with as few bits as possible while meeting the
minimum requirement of reconstruction of the original.
• In the context of this book, we regard data compression (or
compression in short) as algorithms to achieve the
compression goals on the source data.
• Behind each algorithm there are ideas, mathematical
models or implementation techniques to achieve the
compression.
Data compression cont…
• When working on compression problems, we need to
consider the efficiency aspect of the algorithms as
well as the effectiveness of compression.
• Intuitively, the behavior of a compression algorithm
would depend on the data and their internal
structure.
• The more redundancy the source data has, the more
effective a compression algorithm may be.
Types of Data compression
• There are two fundamental classes of data
compression technique: those that lose data and
those that do not.
• Lossy data compression removes some actual data but
leaves enough remaining data for the compressed
format to be still usable; however, it is not reversible.
• A classic example is the reduction of the spatial
resolution of an image.
Data compression types…
• The lower-resolution image is still recognizable as the same picture,
and thus, the data loss is a useful trade-off between image quality and
file size.
• An important example of where picture quality reduction is desirable
is where they are displayed on web pages.
• The time taken to download images is directly related to the size of
the image file.
• If the purpose of the transfer is only to display on the screen, then
there is no point in transmitting an image that has greater resolution
than the display screen itself.
Data compression types…
• In general, a 12-megapixel image will not look any different to a 1-
megapixel image when displayed on a screen with a resolution of 1
million pixels (which is equivalent to a grid of, e.g., 1000 pixels by
1000 pixels).
• However, the 12-megapixel version of the file would take a lot longer
to download and contribute much more to the level of traffic on the
network.
• Actual data, such as financial data or text in a document, cannot be
subjected to lossy data compression.
Data compression types…
• It would be meaningless to just remove a few characters from each
page of a document to reduce the file size.
• Instead, lossless techniques must be used.
Data compression flow diagram
Lossy vs Lossless compression…
Lossy vs Lossless cont….
Lossy vs Losless..
Lossy vs Lossless..
Types of data compressed data…
Compression types..
• Lossless: a compression that can decode back to exactly the original
data. Typically, reduction performance here is limited.
• Lossy: a compression that decodes back with a controlled deviation
from the original. Here reduction performance is significant (factor
10x and more).
• Lossless compression: The algorithms used to compress the data can
completely reproduce the original data without change.
• As an analogy: If the original data represents an inflated balloon, the
compression takes the air out and the reconstruction brings back the
balloon to its original blown state.
Compression types…
• Examples of compression in computer application would be a zip file or
Web pages for uploading images.
• Lossless compression follows algorithms such as the Lempel–Ziv–Welch
(LZW) Algorithm, arithmetic encoding, Huffman encoding, Shannon Fano
coding.
• These algorithms use a predefined set of character dictionary along with
methodological grouping of numerical characters from input based on
the frequency of repetition.
• Application of lossless compression applies to compression of text or
fundamentally accurate data where every data point has a focus and
function.
Compression types…
• The compression rate of lossless compression is relatively low and
deliberately depends on the frequency of repeated characters in it.
• The required accuracy cripples the application of dynamic statistics
and approximation to it.
• Lossy compression: The lossy algorithms compress to a far large
extent and recreate a very accurate representation of the input data
within defined error limits.
• The analogy used here is: if the original data represents a full car, the
compressed version would be an accurate, small clay model that
represents the full model.
Lossy Compression type…
• That model can be used to produce back the full car with an almost
perfect accuracy.
• Most Images (JPEG), Videos (MP4/H264), Audios (MP3) are
compressed with lossy compression to be able to process and
transmit them quickly and at low (hardware, network and storage)
costs.
• Some of the well-known applied algorithms that segments and
divides data into fragments are: discrete cosine transform, transform
coding, discrete wavelet transform, fractal compression, rectangle
segmentation and Sparse Matrix storage.
Lossy data compression types…
• Focus points within the prioritized data assists the reconstruction
guarantee i.e. the deviation between the original supplied data to the
reconstructed data.
• A major application of this type of compression is in the processing of
images.
• The compression rate of lossy compression is very high compared to
lossless, and the exact level of compression can vary depending on the
algorithms and targeted reconstruction guarantee.
• Almost every digital data ever created in the form of video or image is
processed through a lossy algorithm to attain a workable performance
for a practical application at acceptable costs.
Data compression vs sensor noise
• Every sensor has a natural limitation in its physical accuracy, due to various
factors including electronic noise, environment noise etc.
• This is called: sensor noise, sensor inaccuracy or measurement uncertainty.
• With Teraki technology ([Link]) one can set the maximum
acceptable deviation for the reconstructed data at the same level as the
sensor inaccuracy.
• The allowed maximum deviation (hard bound) is fully configurable and
determined by the customer.
• For instance, a sensor with 1% (telematics) or 2 cm (LiDAR) inaccuracy would
allow each reconstructed data point to deviate with respectively 1% or 2 cm
or less.
Data compression vs sensor noise
cont..
• An accuracy lower than the sensor inaccuracy (noise) is therefore a
meaningless accuracy.
• Using the fact that one cannot be more accurate than the sensor.
• When Teraki technology operates within this sensor noise it delivers
factor 10X or more of data reduction, without any loss
of meaningful accuracy in physical information.
• The maximum allowed deviation can be configured by the customer
and enables to exceed the sensor noise only by a tiny fragment.
• For instance, taking a sensor noise of 2 cm and bring it to (maximum!)
2.1 cm whilst achieving factor 6x reduction.
Compressed images