CS4551 Spring 2020 HW #2
CS4551 Multimedia Software Systems Homework2 (15%) – Vector Quantization and DCT Coding
• Due: Electronic submission via CSNS by Sunday, 04/19/2020.
• What to turn in:
o Submit source code with necessary files for “compile and run”.
o Do NOT submit data files.
o You MUST provide a readme.txt file containing all information to help with the grading process.
• If your program produces any compile errors, you will receive 0 automatically no matter how close your program is to the solution.
• Programming requirements:
o YouarenotallowedtouseanyJavabuilt-inimageclassmethods,library,ortoolstocompletethis
homework.
o Do not create one mega-size main class.
o DonotchangeanygivenmethodsofMImageclassnorcreateanewclassthatduplicatesMImage
class. Treat MImage as a part of imported library.
o Test your program with all test data.
o If you do not meet any of the requirements above, you will receive a significant reduction.
0. What your program should do
Name your main application CS4551_[YourLastName].java (e.g. CS4551_Doe.java) and expand the given template program to perform the following tasks.
Receive the input file as command line arguments.
java CS4551_Doe Ducky.ppm
Read a 24bit input PPM image and display the following main menu to the user and receive the user’s input.
Main Menu———————————– 1. Vector Quantization
2. DCT-based Coding
3. Quit
Please enter the task number [1-3]:
After performing a selected task, go back to display the menu again.
1. Task 1 – Vector Quantization (50 pts)
Compress the 24 bits per pixel input image to 2 bits per pixel using Vector Quantization (VQ). Implement VQ encoding/decoding using the requirements below.
1
CS4551 Spring 2020 HW #2
Encoding:
•
•
•
Input vectors are formed by 2×2 blocks of RGB pixels. Each input vector 𝒙 consists of RGB values of FOUR pixels, P1, P2, P3, and P4, and therefore 𝒙 is 12 dimensional.
Diagram of a 2×2 pixel block of the input image
𝒙 = {𝑃1𝑅,𝑃1𝐺,𝑃1𝐵,𝑃2𝑅,𝑃2𝐺,𝑃2𝐵,𝑃3𝑅,𝑃3𝐺,𝑃3𝐵,𝑃4𝑅,𝑃4𝐺,𝑃4𝐵}
Codebook and codebook vectors: The 2-bits per pixel quantization is equivalent to using 8 bits per 4 pixels. Therefore, the VQ should the vector space into 256 (=28) cells and the codebooks should have 256 entries that are centroids of the 256 cells. After the vector quantization, each vector 𝒙 belongs to one cell and each cell number is represented by 1 byte. In order words, after the quantization, each 2×2 block (4×3=12 bytes) is encoded by a 1-byte codebook index. So, the compression ratio is 12.
Codebook generation: Use K-means clustering algorithm to generate codebook vectors (centroids of cells).
K-means Clustering Algorithm
Inputs: K, number of clusters and the data set (input vectors 𝒙) K is 256 in our case.
Assume that 𝒄[𝑖] store the K centroids. 𝑖 = 0, 1, ⋯ , 255. Each 𝒄[𝑖] is a 12-dimensional vector.
1. Assign randomly generated initial values for the 𝐾 centroids.
2. For each 𝒙,
For each 𝑖 = 0 to 255
If 𝒄[𝑖] is the closest cell (cluster) to 𝒙 based on the Euclidean distance between 𝒙 and 𝒄[𝑖],
assign 𝒙 to 𝒄[𝑖] cluster
3. Updatethe𝐾centroids.
4. Iterate 2 & 3 until the algorithm meets a stopping condition (i.e. no data points change clusters, the sum of the distance is minimized, or the maximum number of iterations is reached.)
Display the codebook. This is equivalent to displaying 𝒄[𝑖], 𝑖 = 0, 1, ⋯ ,255.
Extra credit (10 pts) – Save the quantized image (i.e. indices of all 2×2 blocks) into a PPM file. Given 𝑊 × 𝐻 input image, the quantized image resolution is 𝑊/2 × 𝐻/2. The quantized image is a grayscale image because each pixel is an 8-bit index.
P1
P2
P3
P4
• •
Decoding:
• Given the quantized image and the codebook, for each pixel of the quantized image, recover RGB pixel values of 4 pixels.
• Save the decoded image so that you can compare the output with the input. 2. Task 2 – DCT-based Coding (50 pts)
Implement a DCT-based transform coding. Notice that this is different from the standard JPEG steps. The encoder/decoder steps are shown below.
2
CS4551 Spring 2020 HW #2
E1. Resize Input Image
E3. Forward DCT
E4. Quantization
D4. Restore Original Size
D2. Inverse DCT
D1. De-quantization
E2. Color Conversion & Subsampling
D3. Supersampling & Inverse Color Conversion
Input RGB Image (PPM) Decompressed RGB Image (PPM)
Entropy Encoding/Decoding
Compressed Image 01001…
Encoding Steps
Decoding Steps
E1. Read and resize the input image
Read the input ppm file containing RGB pixel values for encoding. First, if the image size is not a multiple of 8 in each dimension, make (increase) it become a multiple of 8 and pad with zeros. For example, if your input image size is 21×14, make it become 24×16 and fill the extra pixels with zeros (black pixels).
D4. Remove Padding and Display the image
Display the decompressed image. Remember that you padded with zeros if the input image size is not multiple of 8 in both dimensions (width and height). Restore the original input image size by removing extra padded rows and columns.
3
CS4551 Spring 2020 HW #2
E2. Color space transformation and Subsampling
Transform each pixel from RGB to YCbCr using the equation below:
𝑌 0.2990 0.5870 0.1140 𝑅 (𝐶𝑏) = (−0.1687 −0.3313 0.5000 ) (𝐺) 𝐶𝑟 0.5000 −0.4187 −0.0813 𝐵
Initially, RGB value ranges from 0 and 255. After color transformation, Y should range from 0 to 255, while Cb and Cr should range from -127.5 to 127.5. (Truncate if necessary.)
Subtract 128 from Y and 0.5 from Cb and Cr so that they span the same range of values [-128,127]
Subsample Cb and Cr using 4:2:0 (MPEG1) chrominance subsampling scheme. If Cb(Cr) is not divisible by 8, pad with zeros.
D3. Supersampling and Inverse Color space transformation
Supersample Cb and Cr so that each pixel has Cb and Cr.
Add 128 to the values of the Y component and 0.5 to the values of the Cb and Cr components.
If using a color image, transform from the YCbCr space to the RGB space according to the following equation:
𝑅 1.0000 (𝐺) = (1.0000 𝐵 1.0000
0 −0.3441
1.4020 𝑌 −0.7141) (𝐶𝑏)
1.7720 0 𝐶𝑟
Common mistake: After this step, you have to make sure that the resulting RGB values are in the range between 0 and 255. Truncate if necessary.
E3. Forward DCT
Perform the forward DCT for Y image using the following steps:
• Divide the image into 8×8 blocks. Scan each block in the image in raster order (left to right, top to bottom)
• For each 8×8 block, perform the DCT transform to get the values 𝐹 from the values
𝑓 . The elements 𝐹 range from −210 to 210 𝑥𝑦 𝑢𝑣
Check max and min and assign −210 or 210 for the values outside of the range so that the values range from −210 to 210.
Perform the DCT for Cb and Cr images, too.
𝑢𝑣
D2. Inverse DCT
Perform the inverse DCT to recover the values 𝑓 𝑥𝑦
from the values 𝐹 and recover Y, Cb, Cr images. 𝑢𝑣
4
CS4551 Spring 2020 HW #2
Forward DCT Formula
1 7 7 (2𝑥 + 1)𝑢𝜋 (2𝑦 + 1)𝑣𝜋
𝐹 = 𝐶𝐶∑∑𝑓 cos( )cos( ) 𝑢𝑣4𝑢𝑣 𝑥𝑦 16 16
𝑓 𝑥𝑦
𝑥=0 𝑦=0
𝐶𝑢 ={1/√2, 𝑢=0
1, otherwise
𝐶𝑣 ={1/√2, 𝑣=0
1, otherwise
is the 𝑥-th row and 𝑦-th column pixel of the 8×8 image block (𝑥 and 𝑦 range from 0 to 7); 𝐹 𝑢𝑣
is the DCT
coefficient value in the 𝑢-th row and 𝑣-th column (𝑢 and 𝑣 range from 0 to 7). Inverse DCT Formula
1 7 7 (2𝑥+1)𝑢𝜋 (2𝑦+1)𝑣𝜋
𝑓′ = ∑∑𝐶 𝐶 𝐹′ cos( )cos( 𝑥𝑦4𝑢𝑣𝑢𝑣 16 16
)
𝑢=0 𝑣=0
E4. Quantization
Given 𝐹 𝑢𝑣
specified in Table 1 and Table 2.
In this homework, we want to provide a variety of compression quality options (high compression or low compression). User shall specify one parameter 𝑛 (0 ≤ 𝑛 ≤ 5), which controls the quality of the compression by changing the quantization intervals. The actual quantization is done by
in an 8×8 DCT block, quantize 𝐹 𝑢𝑣
𝐹 Quantized(𝐹 ) = round ( 𝑢𝑣 )
using:
𝑢𝑣
The default intervals 𝑄𝑢𝑣 corresponding 𝑢 and 𝑣 are
Quantized(𝐹 ) = round ( 𝑢𝑣
𝑄′ =𝑄 ×2𝑛 𝑢𝑣 𝑢𝑣
𝐹
𝑢𝑣 )
𝑄′ 𝑢𝑣
𝑄𝑢𝑣
Forexample,if𝑛=0,𝑄′ issameas𝑄 ;if𝑛=1, 𝑢𝑣 𝑢𝑣
𝑄′ is double of 𝑄 , which will divide 𝐹 with 𝑢𝑣 𝑢𝑣 𝑢𝑣
bigger values and result in more compression.
D1. De-quantization
Assume that the quantization tables (basis ones) and
the compression quality parameter 𝑛 are available for
decoding. Given the quantized value for DCT
coefficient 𝐹 , multiply it by the corresponding 𝑢𝑣
quantization interval 𝑄′ . 𝑢𝑣
𝐹′ = Quantized(𝐹 ) × 𝑄′ 𝑢𝑣 𝑢𝑣𝑢𝑣
Notice that the recovered 𝐹′ will be different from
the original 𝐹 . 𝑢𝑣
𝑢𝑣
5
CS4551
Spring 2020 HW #2
Default Quantization Tables
The following table gives the default quantization intervals for each element in the 8×8 DCT block for the luminance (Y) and chrominance (Cb and Cr).
Table 1. Luminance Y Quantization Table 2. Chrominance Cb and Cr Table Quantization Table
4
4
4
8
16
8
16
16
32
8
8
8
32
16
16
32
64
32
64
4
4
8
8
16
16
32
32
8
8
16
16
32
32
64
64
4
8
8
16
16
32
32
32
8
16
16
32
32
64
64
64
8
8
16
32
32
32
32
16
16
32
64
64
64
8
16
16
32
32
32
32
48
16
32
32
64
64
64
64
96
16
16
32
32
32
32
48
48
32
32
64
64
64
64
96
96
16
32
32
32
32
48
48
48
32
64
64
64
64
96
96
96
32
32
32
32
48
48
48
48
64
64
64
64
96
96
96
96
• E1/D4 – 10 pts
• E2/D3 – 10 pts
• E3/D2 – 20 pts
• E4/D1 – 10 pts
An important requirement – After each encoding step, implement the corresponding decoding step immediately and check if your output is correct or not.
You will receive credits for each encoding step if only if you complete to implement the corresponding decoding step.
Sample results will be posted on CSNS.
6