MA304: Topics in Applied Mathematics

Unit 2: Data Compression   A natural continuation of DDR studied in Unit 1 is the subject of data compression.  To prepare for this investigation, we will introduce the discrete Fourier transform (DFT).  For efficient computation, we will introduce the fast Fourier transform (FFT) for computing the n-point DFT, for n equal to an integer power of 2.  A real-valued version of the DFT, called discrete cosine transform (DCT), is derived for application to image compression.  The importance of DFT and DCT is their functionality to extracting frequency content of discrete data.  A given data set may be considered as an information source, and the histogram of the source gives rise to its probability distribution, which in turn is used to define the entropy of the source.  In this unit, you will study information coding, including Shannon’s Noiseless Coding theorem and construction of the Huffman code, for reversible (or lossless) compression of the data.  To significantly improve the compression efficiency, DCT followed by an appropriate quantization may be applied to reduce the entropy.  This procedure is irreversible, but certainly most effective, particularly for image and video compression.  In this regard, you will study the JPEG image compression standard and the video compression scheme.  This discussion includes the necessity of color transform.

Unit2 Learning Outcomes
Upon successful completion of this unit, the student will be able to:
- Compute the DFT of column vectors. - Compute DCT of column vectors. - Compute the histogram of a data set. - Compute the probability distribution of an information source based on its histogram. - Compute the entropy of an information source based on the probability distribution. - Build Huffman trees based on the probability distribution. - Construct Huffman code-tables. - Compute two-dimensional DCT of a matrix. - Apply given quantization tables to the DCT matrix. - Perform color transformation. - Outline the JPEG compression scheme.

2.1 Discrete and Fast Fourier Transform (FFT)   - Lecture: MIT: Professor Gilbert Strang’s Linear Algebra: “Lecture 17: Orthogonal Matrices and Gram-Schmidt” Link: MIT: Professor Gilbert Strang’s Linear Algebra: “Lecture 17: Orthogonal Matrices and Gram-Schmidt” (YouTube)

Instructions: Please click on the link above, and view the entire video to learn about Orthogonal matrices, Gram-Schmidt orthogonalization process. You may also click on the tab for “Transcript,” and download the transcript to read along with the video lecture.
Viewing this lecture and pausing to take notes should take approximately 1 hour to complete.

2.1.1 Definition of DFT   Note: This topic is covered by the lectures assigned below subunit 2.1.

2.1.2 Lanczos’ Matrix Factorization   - Reading: Lanczos’ Matrix Factorization The Saylor Foundation does not yet have materials for this portion of the course. If you are interested in contributing your content to fill this gap or aware of a resource that could be used here, please submit it here.

``````[Submit Materials](/contribute/)
``````

2.1.3 FFT for Fast Computation   Note: This topic is covered by the lectures assigned below subunit 2.1.

2.2 Discrete Cosine Transform (DCT)   - Reading: Discrete Cosine Transform (DCT) The Saylor Foundation does not yet have materials for this portion of the course. If you are interested in contributing your content to fill this gap or aware of a resource that could be used here, please submit it here.

``````[Submit Materials](/contribute/)
``````

2.2.1 Derivation of DCT from DFT   2.2.2 8-point DCT   2.2.3 2-dimensional DCT   2.3 Information Coding   - Reading: Information Coding The Saylor Foundation does not yet have materials for this portion of the course. If you are interested in contributing your content to fill this gap or aware of a resource that could be used here, please submit it here.

``````[Submit Materials](/contribute/)
``````

2.3.1 Probability Distribution   2.3.2 Histogram   2.3.3 Entropy   2.3.4 Binary Codes   2.4 Data Compression Schemes   - Lecture: YouTube: National Program on Technology Enhanced Learning (NPTEL)’s “Lecture 19: Data Compression” Link: YouTube: National Program on Technology Enhanced Learning (NPTEL)’s “Lecture 19: Data Compression” (YouTube)

Instructions: Please click on the link above, and view the entire lecture for an overview of data compression.  Please note that this video also covers the topics outlined in sub-subunits 2.3.3, 2.4.1, and 2.4.3.
Viewing this lecture and pausing to take notes should take approximately 1 hour to complete.

2.4.1 Lossless and Lossy Compression   Note: This topic is covered by the lecture assigned below subunit 2.4.

• Lecture: YouTube: National Programme on Technology Enhanced Learning (NPTEL)’s “Lecture 17: Lossy Image Compression: DCT” and “Lecture 18: DCT Quantization and Limitations" Links: YouTube: National Programme on Technology Enhanced Learning (NPTEL)’s “Lecture 17: Lossy Image Compression: DCT” (YouTube) and “Lecture 18: DCT Quantization and Limitations” (YouTube)

Instructions: Please click on the links above, and view these video lectures to learn about lossy image compression.  The first video is on DCT, and the second video is on quantization of DCT and its limitations.
Viewing these videos and pausing to take notes should take approximately 2 hours and 30 minutes to complete.

2.4.2 Kraft Inequality   - Reading: Kraft Inequality The Saylor Foundation does not yet have materials for this portion of the course. If you are interested in contributing your content to fill this gap or aware of a resource that could be used here, please submit it here.

``````[Submit Materials](/contribute/)
``````

2.4.3 Huffman Coding Scheme   Note: This topic is covered by the lecture assigned below subunit 2.4.

Instructions: Please click on the link above, and view the entire video to learn about Huffman Coding.
Viewing this video and pausing to take notes should take approximately 15 minutes to complete.

2.4.4 Noiseless Coding Theorem   - Reading: Noiseless Coding Theorem The Saylor Foundation does not yet have materials for this portion of the course. If you are interested in contributing your content to fill this gap or aware of a resource that could be used here, please submit it here.

``````[Submit Materials](/contribute/)
``````

2.5 Image and Video Compression Schemes and Standards   - Reading: John Loomis’s “JPEG Tutorial” Link: John Loomis’s “JPEG Tutorial” (HTML)

`````` Instructions: Please click on the link above, and read the entire
webpage to study a tutorial on JPEGs.  Please note that this reading
also covers the topics outlined in sub-subunits 2.5.1 through
2.5.7.
Studying this reading should take approximately 30 minutes to
complete.

displayed on the webpage above.
``````
• Lecture: YouTube: National Program on Technology Enhanced Learning (NPTEL)’s “Lecture 16: Introduction to Image and Video Coding,” “Lecture 23: Video Coding: Basic Building Blocks,” “Lecture 24: Motion Estimation Techniques,” and “Lecture 26: Video Coding Standards” Links: YouTube: National Program on Technology Enhanced Learning (NPTEL)’s “Lecture 16: Introduction to Image and Video Coding” (YouTube), “Lecture 23: Video Coding: Basic Building Blocks” (YouTube), “Lecture 24: Motion Estimation Techniques” (YouTube), and “Lecture 26: Video Coding Standards” (YouTube)

Instructions: Please click on the links above, and view these videos (about 1 hour each) to learn about video compressions methods and standards.  Please note that these video lectures also cover the topics outlined in sub-subunits 2.5.1 through 2.5.7.
Viewing these videos and pausing to take notes should take approximately 5 hours to complete.

2.5.1 Image Compression Scheme   Note: This topic is covered by the lectures assigned below subunit 2.5.

2.5.2 Quantization   Note: This topic is covered by the lectures assigned below subunit 2.5

2.5.3 Huffman, DPCM, and Run-Length Coding   Note: This topic is covered by the lectures assigned below subunit 2.5.

2.5.4 Decoder   Note: This topic is covered by the lectures assigned below subunit 2.5.

2.5.5 I, P, and B Video Frames   Note: This topic is covered by the lectures assigned below subunit 2.5.

2.5.6 Macro-Blocks   Note: This topic is covered by the lectures assigned below subunit 2.5.

2.5.7 Motion Search and Compensation   Note: This topic is covered by the lectures assigned below subunit 2.5.