Compression | Sahithyan's Notes

Compression reduces the volume of data required to represent an image, without necessarily reducing its information content. It works by removing data redundancy.

Lossless compression
Source and reconstructed image match pixel to pixel.
Lossy compression
Source and reconstructed image may not match pixel to pixel.

Compression Ratio

For the same information encoded with $n_1$ units of data under scheme $C_1$ and $n_2$ units under scheme $C_2$ :

CR = \frac{n_1}{n_2}

Relative data redundancy of $C_2$ compared to $C_1$ :

RD = 1 - \frac{1}{CR}

Compression Pipeline

A compression system has an encoder and a decoder. The encoder is a chain of 4 stages. Each stage targets 1 kind of redundancy.

\text{Mapper} \to \text{Quantizer} \to \text{Symbol encoder} \to \text{Channel encoder}

Decompression runs the inverse of each stage in reverse order. The quantizer has no inverse, so a pipeline containing it is lossy.

Mapper

Transforms the pixel array into a representation where interpixel redundancy is exposed. The mapping is reversible and loses no information.

Examples:

Run-length encoding, which replaces a run of equal pixels by the pixel value and the run length
Predictive coding, which stores the difference between each pixel and its prediction from neighbours
Transform coding, which stores coefficients of a transform such as the DCT

Quantizer

Reduces the number of distinct values the mapper output can take, so fewer bits per value are needed. It removes psychovisual redundancy by discarding detail the eye barely perceives.

Irreversible, so it is the only stage that makes the pipeline lossy
Optional, and omitted in lossless compression
Coarser quantization gives a higher $CR$ and a lower reconstruction quality

Symbol Encoder

Assigns a code to each quantized value. Short codes go to frequent values and long codes to rare values. It removes coding redundancy.

Reversible
The average code length approaches the entropy of the source

Examples:

Huffman coding
Arithmetic coding
LZW coding

Channel Encoder

Adds controlled redundancy to the compressed bitstream. The decoder uses it to detect and correct errors from storage or transmission, since a compressed stream has little natural redundancy left to survive a bit error.

Examples:

Parity bit
Hamming code