2022/5/16 21:22 Midterm Exam Solution: CS 4551-01 (35846)
Midterm Exam Solution
Part I Concept Problems
Q1~Q4 are drawn from the following question bank:
Copyright By PowCoder代写 加微信 powcoder
The scanning format of one video may be interlaced or progressive .
Error Diffusion algorithm is widely used in converting 8-bit grayscale image to binary image because it could significantly improve the binary image quality. The two steps in the Error Diffusion algorithm are quantization and error diffusion .
Digitization converts analog signals to digital codes, while interpolation recovers original signals from digital codes.
The signal digitization process consists of two steps: sampling and quantization .
The term to describe the domain interval in sampling is sampling period , and the term to describe the range interval in quantization is quantization step .
The two main tasks in vector quantization algorithm are codebook generation and mapping input vectors to an optimal codebook .
The sibling property must be maintained in Adaptive Huffman tree; if it’s about to be violated, a swap procedure is invoked to update the tree by rearranging the nodes.
When there are only 2 symbols in the alphabet set, Huffman coding doesn’t reduce the average symbol length at all (it’s 1 bit/symbol and exactly the same as fixed-length coding). In this case, extended Huffman coding or arithmetic coding can be employed to improve the coding efficiency.
Part II Computation Problems
Q5. For one 240×160 8-bit color image, the maximum number of possible colors is 256 and the file size is 38400 bytes (or 37.5 KB) (ignoring file header and data is uncompressed).
Hint: Use 1 KB = 210 bytes, 1 MB = 220 bytes.
The number of color is 2BD and the file size is WxHxBD/8 bytes, where BD is bit depth per pixel. Results for other images are as follows:
Image 480×320 8-bit color
480×512 8-bit color
Number of Colors
File Size (bytes)
128000 or 125 K
245760 or 240 K
Q6. One 24-bit true color image is converted into one 8-bit indexed color image using Uniform Color Quantization. Let’s consider one pixel with value of (R, G, B) = (208, 231, 36).
https://calstatela.instructure.com/courses/73236/pages/midterm-exam-solution?module_item_id=4511339 1/7
2022/5/16 21:22 Midterm Exam Solution: CS 4551-01 (35846)
A. The 8-bit index value (in decimal) produced by UCQ is 220 .
B. The 3-byte RGB value for this index in the Loop Up Table is (R, G, B) = ( 208 , 240 , 32 ).
Results for other pixel values:
Pixel Value (233, 24, 140)
(161, 71, 245)
(36, 107, 234)
8-bit Index
RGB Value in LUT
(240, 16, 160)
(176, 80, 224)
(48, 112, 224)
Q7. wants to use Vector Quantization technique to compress true color images (24 bits/pixel). She divides the image into 2×2 blocks of RGB pixels and employs 4-bit indexes for codewords. The dimension of the input vector space is 12 , the number of entries in the codebook is 16 , and the compression ratio is 24 .
The VQ’s vector dimension is BWxBHx3, the codebook size is 2BD, and the compression ratio is BWxBHx24/BD, where BW/BH is the block width/height, BD is the bits per vector.
Results for other VQ settings:
3×2 6 18 64 24
3×4 8 36 256 36
Q8. Suppose we are recording music using a microphone with cut-off frequency of 80 KHz under the 5-channel (front left, front right, center, surrounding left, and surrounding right) configuration. We use an ADC (Analog-to-Digital Converter) to digitize the output of the microphone, and then we write the digital signal onto a disk with size 150 MB. Assume 1 KB = 210 bytes and 1 MB = 220 bytes.
A. What is the minimum sampling period we should use if we want to be able to record at least 6 minutes of music using 16 quantization bits per channel?
B. What is the pre-filter’s bandwidth we should use in order to avoid aliasing?
C. Suppose that we want to copy these 6 minutes of music that was recorded on the 150 MB disk
onto a 70 MB flash memory. So, we attempt to reduce the size of the music content by subsampling. Which subsampling ratio should we use to make sure that all 6 minutes of music will fit into the new memory? The subsampling ratio should be an integer, not a float.
D. What is the pre-filter’s bandwidth to avoid aliasing for this subsampling processing?
Hint: Please show your steps.
A. The maximum sampling frequency is
Block Size
Bits of Index
Number of Entries
Compression Ratio
https://calstatela.instructure.com/courses/73236/pages/midterm-exam-solution?module_item_id=4511339 2/7
2022/5/16 21:22 Midterm Exam Solution: CS 4551-01 (35846)
The minimum sampling period is
B. Due to the Nyquist sampling theorem, the maximum signal frequency is no more than half of the sampling frequency. The bandwidth of the pre-filter is
C. The subsampling ratio is
D. The new sampling frequency becomes
And the bandwidth of the pre-filter for subsampling processing is
Results of other settings:
Sampling Period
Sampling Pre- filter Bandwidth
Subsampling Ratio
Subsampling Pre-filter Bandwidth
200 MB, 8 min, 80 MB
22.8882 μs
21.8453 KHz
7.2818 KHz
300 MB, 10 min, 130 MB
19.0735 μs
26.2144 KHz
8.7381 KHz
Q9. Suppose that you have an alphabet set consisting of four symbols {A, B, C, D} with the probabilities ( )=0.21, ( )=0.16, ( )=0.53, ( )=0.10.
A. Design the VLC codes for these symbols using algorithm. You may draw graph or write down to illustrate the node merging steps.
B. Encode the message “BADB” with the generated Huffman codes.
C. What is the average symbol length for this Huffman coder?
D. What is the coding efficiency of this Huffman coder?
Hint: Please show your steps; the graph of Huffman coding’s merging steps can be submitted at the last dummy problem.
A. The Huffman coding’s merging is as follows;
https://calstatela.instructure.com/courses/73236/pages/midterm-exam-solution?module_item_id=4511339 3/7
2022/5/16 21:22 Midterm Exam Solution: CS 4551-01 (35846)
The VLC codes generated are
Symbol Code Length A 00 2
B. The message “BADB” is encoded as
C. The average symbol length is
D. The entropy is
The encoder’s efficiency is
011 00 010 011
Due to the freedom in labeling branches in Huffman coding, the VLC codes generated and the encoded message depend on the specific design. The results om average symbol length and encoder efficiency are as as follows:
Probability Average Symbol Length Encoder Efficiency
( )=0.04, ( )=0.24, ( )=0.16, ( )=0.56
1.6400 bits
( )=0.28, ( )=0.04, ( )=0.56, ( )=0.12
1.6000 bits
Q10. Compress the message “BACBACBAC” with LZW algorithm.
https://calstatela.instructure.com/courses/73236/pages/midterm-exam-solution?module_item_id=4511339 4/7
𝐷𝑃 𝐶𝑃 𝐵𝑃 𝐴𝑃
𝐷𝑃 𝐶𝑃 𝐵𝑃 𝐴𝑃
2022/5/16 21:22 Midterm Exam Solution: CS 4551-01 (35846)
Please fill the following blanks with the longest matching patterns, encoder output (index), and the new codebook entries generated during this process.
Codebook Index Entry
Hint: Only fill one matching pattern, encoder output, or codebook entry in each cell; put “-” in empty cells.
Results of Compressing Message “BCABCABCABCA”
Codebook Index Entry
https://calstatela.instructure.com/courses/73236/pages/midterm-exam-solution?module_item_id=4511339 5/7
2022/5/16 21:22 Midterm Exam Solution: CS 4551-01 (35846)
Results of Compressing Message “CBACBACBACBA”
Codebook Index Entry
Q12. Let’s consider the lossless mode of JPEG. For prediction per pixel, one of four candidate predictors , , , or + − will be chosen, and the selection criterion is the maximum number of available neighboring pixel values.
Suppose that we have the following 4×4 image to encode:
38 38 37 37 40 39 34 30
37 37 37 33
30 38 32 30
Put the values in the following cells of the encoded image.
38 0 -1 0 2 -1 -4 -4
Another 4×4 image to encode:
https://calstatela.instructure.com/courses/73236/pages/midterm-exam-solution?module_item_id=4511339 6/7
2022/5/16 21:22 Midterm Exam Solution: CS 4551-01 (35846)
Encode image
Third 4×4 image to encode:
Encoded image:
41 50 48 44
48 40 48 46
47 44 42 47
43 44 45 48
41 9 -2 -4 -7 -17 10 2
-1 5 -10 7
53 51 56 55 57 52 52 57
57 60 58 59
52 53 53 60
53 -2 5 -1 4 0 -8 6
https://calstatela.instructure.com/courses/73236/pages/midterm-exam-solution?module_item_id=4511339 7/7
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com