Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Question 1
(a) [COMP3491 - May 2023 exam]
Encode the following sequence
traduttore
of ten characters using arithmetic coding.
[15 Marks]
(b) [COMP3491 - May 2023 exam]
Encode the following sequence
traduttore=traditore
of twenty characters using
i. Huffman coding;
[7 Marks]
ii. LZ78 (you may assume that there is an “End of file” character at the
end).
[8 Marks]
Show all your work.
(c) For the triangle mesh in the figure below, write the encoding sequence
of CLERS symbols produced by the Edgebreaker algorithm. The arrow
indicates the gate. Explain your answer.
[10 Marks]
continuedPage 2 of 4 COMP3687 - MOCK EXAM
(d) In the PNG traversal of the pixels of an image, the shaded cells of the
table show the values of three already processed pixels. For each of the
five filters of the PNG compression algorithm, compute the prediction for
the value of the pixel x.
50
65
20
x
[10 Marks]
End of Section A continuedPage 3 of 4 COMP3687 - MOCK EXAM
Section B Lossy Compression
Dr Mark Gotham
Question 2
(a) Below are two 6x6 grids from corresponding parts of consecutive frames
in a simple video. The block search algorithm is applied to seek the best
match.
Frame 1:
Frame 2:
[P.T.O. for questions]
continuedPage 4 of 4 COMP3687 - MOCK EXAM
i. What is the distance in vertical and horizontal steps (m, n) of the best
match between the two frames, measuring from frame 1 to frame 2.
ii. What is the mean square difference between the two parts in this
best-matching comparison.
iii. What are the minimum dy and dx values needed to spot this match?
iv. For the minimum dy and dx pair in your last answer, what is the total
number of comparisons made? Show your working.
[16 Marks]
(b) Write out the numbers of the matrix X (below) in the order that a zigzag
scan would encounter them.
0 1 2 3 4 5
6 7 8 9 10 11
12 13 14 15 16 17
18 19 20 21 22 23
24 25 26 27 28 29
30 31 32 33 34 35
[9 Marks]
(c) (This question is from the 2022-23 exam.) You are asked to design a
compression algorithm aimed at archiving digitised books. Discuss what
aspects of the problem will influence your design, and how the techniques
viewed in the lectures are appropriate for this problem. You are not re
quired to actually design an algorithm. (Approximate word count: 200)
[25 Marks]