Compression Techniques in Multimedia System

1. What is compression technique?
The techniques used for data compression is called compression technique. Compression technique is the process of encoding information using fewer bits through use of a specific encoding scheme.
2. Significance of compression techniques in multimedia system
There is much significance of compression techniques in multimedia system. With the techniques we get less disk space for data, faster reading and writing, faster file transfer, variable dynamic range and byte order independence.
3. Coding requirements in compression techniques
The basic coding requirements for compression techniques are storage, throughput and interaction.
Multimedia elements require much more space than text element, for example one second of uncompressed CD quality stereo audio is 176400 bytes and a true color full screen image requires 921600 bytes.
Continuous media requires a large amount of processing power that is throughput like uncompressed CD quality stereo audio stream needs 176400 bytes per second.
Multimedia system requires fast interaction between the sending and receiving ends, thus end to end delay should be small like video conference needs a delay less than 50 ms.


4. Classification of coding method
There are two kinds of coding method in multimedia system. They are,
  1. Lossless
  2. Lossy
Lossless compression is that type of compression where the amount of data or information is not reduced and from where the original data can be reconstructed.
Lossy compression is that type of compression where the amount of information is reduced during the compression and an approximate of original data can be reconstructed during decompression.
5. Categories of compression technique
There are three major category of compression technique and they have their own sub categories. All the categories are given below.
  1. Entropy coding
    1. Run length coding
    2. Huffman coding
    3. Arithmetic coding
  2. Source coding
    1. Prediction
      1. DPCM
      2. DM
      3. Transformation
        1. FFT
        2. DCT
      4. Vector quantization
  3. Hybrid coding
    1. JPEG
    2. MPEG
    3. H.261
6. Coding techniques
There are various kinds of coding techniques and they are stated below.
  1. a. Vector quantization:
In this technique a data stream is divided into smaller blocks of byte and then each block is coded with a predefined patterns stored in a table.
  1. b. LZW:
In this technique a data dictionary of data patterns are created observing the occurrence of data in an uncompressed data stream. And when there is a match with the patterns the output is taken from that table.
  1. c. Differential coding:
In this technique the difference between the consecutive samples are calculated instead of the sample values.
7. Run length coding
Run length coding is that type of compression technique where the sequences of same bytes are replaced with a flag and the number of the occurrences. As a flag any unused special symbol that is not in the stream is used.  From an example it will be clearer,
Let a data stream contains      AAAAABCDDDDDDF
Now the Run length coding of this stream will be like          A!5BCD!6F
Another variation of run length coding is known as tabulators. In this technique tables of symbols are predefined to replace the sequences of different lengths of identical bits or bytes.
8. Huffman coding
Huffman coding is an entropy coding technique to compress data in which frequent events are represented by short codes, and rare events are represented by long codes.
A Huffman code tree can be produced by following the steps,
  1. Sort all the symbols as a decreasing probability.
  2. Combine the two lowest symbol into one
  3. Sort all the new symbols including the new one
  4. These steps will be repeated until there is only one symbol and a binary tree is there.
  5. 0 is assigned for the left node and 1 is assigned for right node
An example is given below,
Let there is a set of symbols with probabilities and that is
m0(0.10), m1(0.36), m2(0.15), m3(0.20) and m4(0.19)
From this set Huffman tree is like the following

And the resultant code words are
Symbols Probability Codewords
m0 0.10 011
m1 0.36 00
m2 0.15 010
m3 0.20 10
m4 0.19 11
9. JPEG
JPEG stands for Joint Photographic Experts Group. This method can be applied to grayscale or color image. There are three levels of definition for JPEG. They are,
# Baseline system which reasonably decompress color images and maintain a high color ratio and handles 4 bits per pixels to 16 bit per pixels
# Extended system which covers the various encoding aspects such as variable-length encoding, progressive encoding, and hierarchical mode of encoding.
# Special lossless function which ensures that resolution at which if decompression is applied no loss of any detail that was in the original image.
9.1. JPEG compression process
There are four steps in jpeg compression process. First one is Preparation, second one is processing, third one is quantization and the fourth one is entropy encoding.
9.2. JPEG – Preparation
In this phase there are some criteria that must be fulfilled and those are,
# There must be a source image that contains at least one plane and at most 255 palnes
# Each plane may have different numbers of pixels in horizontal and vertical dimensions
# The resolution of individual plane may be different
# Each pixel is represented by number of bits ,p where p is greater than or greater than equal 2 and less than or less than equal 12
# The image is divided into 8X8 blocks
9.3. JPEG – Discrete Cosine Transform (DCT)
This is the processing phase of jpeg compression technique. In this process data are transformed from spatial domain to frequency domain, in this phase data redundancy is removed. And this DCT is a symmetrical algorithm and the reverse DCT algorithm can be used to decompress an image.
9.4. JPEG – Quantization
In this phase the DCT output matrix is quantized to reduce precision of the coefficients to increase the compression.
DCT (0, 0) is known as DC coefficient and other DCT coefficients are known as AC coefficients. And this DC coefficient can be dropped to reduce data size.
A set of quantized table is defined at JPEG baseline algorithm and there is a formula for calculating quantized coefficients Q.
Qij=DCTij/qij
9.5. JPEG – Entropy Encoding
Entropy coding is a special form of lossless data compression. It involves arranging the image components in a "zigzag" order employing run-length encoding algorithm that groups similar frequencies together, inserting length coding zeros, and then using Huffman coding on what is left.
In this phase,
# The DC coefficients are treated separately from the AC coefficients
# A DC coefficient is encoded as the difference between the current coefficient and the previous one
# The AC coefficients are encoded using Huffman and/or arithmetic encoding
10. MPEG
MPEG stands for Moving Pictures Expert Group. MPEG has a data rate of 1.2 Mbits per second. MPEG can be both used for symmetric and asymmetric compression. In preparation stage MPEG defines the format of the image and each image consists of three components YUV and for each component a pixel is coded with 8 bits.
10.1. How MPEG encode the video stream
MPEG uses a temporal prediction technique to encode the frame thus storage requirement greatly reduces. There are four basic kinds of frames in common MPEG data stream. They are,
# I-frame (Intra-frame) which is a self contained frame and it is coded without reference to any other frames.
# P-frame (Predictive-coded frame) which is coded using the predictive technique with reference to the previous I-frame and/or previous P-frame.
# B-frame (Bi-directionally predictive coded frame) which requires information of the previous and following I- and P-frames for encoding and decoding.
# D-frame (DC-coded frame) Only the lowest frequency component of image is encoded. It is used in fast forward or fast rewind.
10.2. Group of Pictures
When the video is encoded and transferred most often the I,P and B frames are arranged into a group named group of pictures which contains twelve frames at the following order IBBPBBPBBPBB.
10.3. I-Frame encoding
I frames are encoded using JPEG compression technique but the compression takes place in real time which needs  33 ms for  30 frames per second video streaming.
11. MPEG-2
MPEG – 2 is the newer version video encoding standard which is based on MPEG-1. This technology supports higher video quality and higher data rate that is up to 80 Mbits per second.
Summary
There are various techniques for multimedia compression. Run length and Huffman coding is popularly used for the data compression. Even in JPEG and MPEG encoding Huffman coding is used in the processing phase for encoding. For Image compression there is JPEG encoding standard and for the video data compression there is MPEG-1 and MPEG-2 encoding standard

2 comments:

Subscribe to: Post Comments (Atom)