Hello, dear friend, you can consult us at any time if you have any questions, add WeChat:THEend8_
Homework2 (15%) – Vector Quantization and DCT Coding
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 You are not allowed to use any Java built-in image class methods, library, or tools to complete this
homework.
o Do not create one mega-size main class.
o Do not change any given methods of MImage class nor create a new class that duplicates MImage
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.
<eg> On Command Prompt
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.
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.
P1 P2
P3 P4
Diagram of a 2×2 pixel block of the input image
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