Multimedia Lecture 3: Data Compression

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.