Compression Techniques
Compression Techniques

The aim of compression is to remove irrelevant and redundant information from the original data in order to transmit or store it more effectively, e.g. use less bandwidth or storage space. It is done by encoding the information using fewer bits than are used in the original representation.

The amount of data which is created by today’s multimedia devices is huge. If we wanted to store an uncompressed 6 megapixel image (3000x2000 pixels with 8 bits/colour) to a USB stick we would need more than 17 megabytes of space (exactly 18 million of bytes). The exactly same image compressed using the JPEG coder would only require around 3 megabytes of storage space (about 3 200 000 bytes), and you would not notice any difference. The same applies not only to pictures but also to audio and video signals, both for storage and for transmission across digital networks.

The compression algorithms can be divided into:

- Lossless coding
- Lossy coding

Lossless compression reduces bit by finding and reducing statistical redundancy, i. e. information which is repeating or can be determined from other information in the signal. Lossless compression (also known under the term compaction) allows us to reconstruct the original signal without any modification. It is therefore suitable for archival purposes.

Lossy compression, on the other hand, attempts to reduce the amount of data by eliminating information which cannot be perceived due to imperfections of human senses. When this type of compression is used, the reconstructed signal is never the same as the original. It is suitable for applications where limited bandwidth or storage occurs.

Generally, lossy algorithms are far more effective than lossless algorithms, however, the reconstructed signal is always different from the original one. Also, the quality of a compressed signal is the trade-off between the amount of information removed from the original signal and the desired file size of the compressed signal.

There is a measure of changes in the signal which are still acceptable without perceivable difference from the original signal, called the just-noticeable distortion (for speech and audio) or just-noticeable difference (for pictures and video), jnd.

There is a compression ratio to express the efficiency of a compression method, given by formula:

,

where Nn is the count of bits of an uncompressed signal and Nk is the count of bits of a compressed signal.

The software which performs coding of the original signal to the compressed version and decoding the compressed signal into the original signal’s reconstruction is called the codec (a short for encoder-decoder).

## Compression model

There are 3 basic phases in the process of compression:

1. Input data decorrelation
2. Entropy reduction
3. Lossless coding

General compression scheme

Input data decorrelation removes duplicate information from the signal. It can be performed in various ways, or different domains, respectively:

- Time (or space) domain
- Parametric domain
- Signal decomposition

In time (or space) domain, the methods are based on linear prediction which assumes that the neighbouring samples in the time (or space) domain are correlated. The signal decomposition approach splits the signal into subbands allowing monitoring of the energy in each subband separately. The parametric domain applies a specific transform of the input data into the parametric space in order to extract characteristic parameters for coding and transport of the input data.

Entropy reduction is performed using quantization. Even though quantization always brings the loss of information sufficiently detailed quantization makes the loss irrelevant.

The final step in the compression process is lossless coding, or entropy coding where statistically frequent combinations of bits (symbols) are coded with a shorter code word and statistically less common bit combinations are coded with longer code words. This coding is also called the variable length coding (VLC), because the code words are of different length, and is lossless. The most efficient algorithm to perform VLC entropy coding is Huffman coding.

Two modes exist when transporting the compressed information through the transport channel:

- Constant bitrate
- Variable bitrate

When using constant bitrate the coder output is stored in a buffer to maintain constant output bitrate into the transport channel. The bitrate influences the coder in a way that it produces the same bitrate. In this way, the coder can change the quantization steps and thus the quality of the reconstructed signal varies.

Encoder with constant bitrate output

When variable bitrate is used there is no need for the buffer and the coder may use quantization steps according to the necessities of the coded input signal. Quality of the reconstructed signal is constant.

Encoder with variable bitrate output

It may seem that variable bitrate is the best solution. This is only true if the transport channel’s capacity is sufficient for the highest bitrates the variable bitrate coder may produce. On the other hand, if only limited capacity transport channel is available constant bitrate may be more suitable to maintain continuous data stream.