Multimedia Lecture 3: Data Compression

Study Notes

Why Compression

Data compression is necessary to decrease storage requirements and effectively use communication bandwidth, reducing the amount of data without losing information.
Compression improves program execution speed by reducing disk access times and increases data security.

Data Compression Metrics

For data transmission, the goal is speed, which depends on the number of bits sent, and data compression helps in this situation.
Utilization of available bandwidth is another goal of data compression.
Time required for the encoder to generate the coded message and the time required for the decoder to recover the original message are also important factors.

Importance of Data Compression

Large image files require significant storage, e.g., a low-resolution, TV-quality, color video image requires 6.3 Mb per image.
Medical imaging, satellite images, and digital libraries require massive storage, and data compression is necessary to make them manageable.
A medium-sized hospital generates terabytes of data each year.

Compression Requirements

Approximate bit rates for uncompressed sources are:
- Video: 221 Mb/s
- CIF (Videoconferencing): 75 Mb/s
- CCIR (TV): 300 Mb/s
- HDTV: 1.3 Gb/s
The gap between available bandwidth and required bandwidth can be filled using compression.

Why Compression Now

Enabling technology: computers, digital communication, wireless communication, and a solid foundation of 25-50 years of research and development of algorithms.
VLSI technology, high-speed microprocessors, and DSPs have made compression possible.
A better model of perceptually based distortion measures for images and video data is available.
Proliferation of standards has made compression necessary.

Standards

Facsimile: Group 3 and Group 4, JBIG
Still Images: JPEG (0.25-2 bit/pixel), JPEG-2000
Video: MPEG1 (1.5 Mb/s), MPEG2 (6-10 Mb/s), MPEG-2000
High-quality audio: 84/128/192 kbs/s per channel
There are at least 12 audio standards, including a few new standards used for cellular phones.

Compression Algorithms

Huffman, arithmetic, compress, Gzip, and Bzip2 are popular compression algorithms.
An emerging new algorithm is Bzip2.

Data Compression Types

Lossless compression: perfectly recovers original data, e.g., variable length binary codewords.
Lossy compression: reconstructed data is an approximation of the original data, e.g., quantization and compression.

Data Compression and Encryption

Data compression is a kind of encryption for ordinary users.
Encryption also increases the number of bits, making the message secure.

Historical Examples

Grade 1 Braille (1820s) achieved 67% compression.
Morse Code (1835) achieved 8.5 time units for English text.

Ad hoc Techniques

Irreversible compression: run-length encoding, bit mapping, packing into a smaller number of bits, move to front, and differential coding.
Run-length encoding example: compressing a 50-bit message to 40 bits using run-length encoding.
Bit mapping example: compressing a 320-bit message to 40 bits and 272 bits using bit mapping.
Move-to-front encoding: maintaining the alphabet A of symbols as a list where frequently occurring symbols are located near the front.

Description

Test your understanding of data compression and its importance in multimedia technology. Learn how compression reduces storage requirements, improves communication bandwidth, and increases program execution speed. Discover the role of data compression in modern applications like digital libraries and medical imaging.