|TCS420||Data Compression||Learning Schedule|
The course covers the theory of quantization and basic concepts in source coding and applications of the theory and concepts to systems that convert analog or high-rate digital signals into low-rate digital representations with or without loss of fidelity. The con-cept of source coding is extended to general descriptions of a statistical information source where various data modeling techniques find useful applications.
The objective of this course is to
- gain a fundamental understanding of data compression methods for text, images, and video, and related issues in the storage, access, and use of large data sets
- select, giving reasons that are sensitive to the specific application and particular circumstance, most appropriate compression techniques for text, audio, image and video information
- illustrate the concept of various algorithms for compressing text, audio, image and video information.
On completion of this course, the students will be able to
- program, analyze Hoffman coding: Loss less image compression, Text compression, Audio Compression
- program and analyze various Image compression and dictionary based techniques like static Dictionary, Diagram Coding, Adaptive Dictionary
- understand the statistical basis and performance metrics for lossless compression
- understand the conceptual basis for commonly used lossless compression techniques, and understand how to use and evaluate several readily available implementations of those techniques
- understand the structural basis for and performance metrics for commonly used lossy compression techniques and conceptual basis for commonly used lossy compression techniques.
Unit I: Compression Techniques
Loss less compression, Lossy Compression, Measures of performance, Modeling and coding, Mathematical Preliminaries for Loss-less compression: A brief introduction to information theory, Models: Physical models, Probability models, Markov models, com-posite source model, Coding: uniquely decodable codes, Prefix codes.
Unit II: The Huffman coding algorithm
Minimum variance Huffman codes, Adaptive Huffman coding: Update procedure, Encoding procedure, Decoding procedure. Golomb codes, Rice codes, Tunstall codes, Applications of Hoffman coding: Loss less image compression, Text compression, Audio Compression.
Unit III: Coding
Coding a sequence, Generating a binary code, Comparison of Binary and Huffman coding, Applications: Bi-level image compression- The JBIG standard, JBIG2, Image compression. Dictionary Techniques: Introduction, Static Dictionary: Diagram Coding, Adaptive Dictionary. The LZ77 Approach, The LZ78 Approach, Applications: File Compression-UNIX compress, Image Compression: The Graphics Interchange Format (GIF), Compression over Modems: V.42 bits, Predictive Coding: Prediction with Partial match (ppm): The basic algorithm, The ESCAPE SYMBOL, length of context, The Exclusion Principle, The Burrows-Wheeler Transform: Move to- front coding, CALIC, JPEG-LS, Multi-resolution Approaches, Facsimile Encoding, Dynamic Markoy Compression.
Unit IV: Scalar Quantization
Distortion criteria, Models, Scalar Quantization: The Quantization problem, Uniform Quantizer, Adaptive Quantization, Non uniform Quantization.
Unit V: Vector Quantization
Advantages of Vector Quantization over Scalar Quantization, The Linde-Buzo-Gray Algorithm.
- The Data Compression Book – Mark Nelson.
- Data Compression: The Complete Reference – David Salomon.
- Introduction to Data Compression – Khalid Sayood, Morgan Kaufmann Publishers.