Drexel University
ECEC 490 Image Processing Architectures
March 19, 2003Final ExamOpen book and notes
Do any 6 problemsAll problems have identical weight
Problem 1. We encode a bitonal image by using a preprocessor that produces a binary output with p(0) = 0.9875, p(1) = 0.0125. The entropy is 0.1 bit.
(a) We use an arithmetic coder that produces almost perfect compression. How many bits does the coder need, on the average, to encode 800 pixels? On the average, how many ‘1’ bits are encoded in the block?
Answer: Since the entropy = 0.1, it will take abut 800*0.1 = 80 bits. Out of these, 800*0.0125 = 10 will be 1’s. (They will require 10*(-log20.0125) = 63.2 bits).
(b) Suppose the preprocessor produces a string of 5 ones (the string 11111). How many bits of code does the arithmetic encoder produce when encoding this sequence?
Answer: The information in a ‘1’ is –log20.0125 = 6.32 bits. 5 ones will require 5*6.32 = 31.6 bits.
Problem 2. An analog signal is digitized producing numbers in the range 0 to 1000. These numbers are quantized with a step of 20.
(a) What is the maximum error between the input of the quantizer and the de-quantized values?
Answer: The maximum error is 10.
(b) Estimate the rms error between the input of the quantizer and the de-quantized value.
Answer: The rms error is 20*sqrt(1/12) = 5.8
(c) How many bits do we need to represent the output of the quantizer if no entropy coding is used?
Answer: There will be about 1000/20 = 50 values, which requires 6 bits.
Problem 3. A 192 by 192 pixel color image is coded by converting to Y, Cb, Cr and subsampling the color components by a factor of 3 in both directions. Y is coded at full resolution.
(a) How many 8x8 blocks are encoded?
There are 192*192/64 = 576 Y blocks, and (192/3)*(192/3)/64 = 64 Cb and Cr blocks. The total is 576+64+64 = 704 blocks.
(b) How many blocks of each type (Y, Cb, Cr) are in the MCE?
There will be 9 Y, 1 Cb, and 1 Cr block.
Problem 4. A video is coded with an I1 B2 B3 P4 B5 B6 P7 B8 B9 P10 B11 B12 P13 picture sequence. The average compression is 6 for I pictures, 12 for P pictures, and 25 for B pictures.
(a) In what order are these pictures encoded?
I1 P4 B2 B3 P7 B5 B6 P10 B8 B9 P13 B11 B12
(b) Compute the average compression.
There is 1 I, 4 P, and 8 B pictures in a group of pictures. The compression is
13/(1/6+4/12+8/25) = 15.9
Problem 5. Assume that a digital television MPEG decoder has computes an 8x8 IDCT in 2 microseconds. It operates by computing 8 point one dimensional IDCT’s.
(a) How much time is required to compute the 1D IDCT?
Answer: An 8x8 2-IDCT requires 16 1-D DCT’s. Therefore the 1-D DCT requires 2/16 = 0.125 microseconds.
(b) How many operations per second must the processor perform?
Answer: Assume that the processor requires 8^2 = 64 operations to perform a 1-D DCT. This means that it must perform about 1 operations every 2 nanosecond, of 500 MOPS.
Problem 6. We are designing a HDTV camera that is to produce an MPEG-2 bitstream in real time. It is to operate with a 1440x1152 format at 30 frames per second and 4:2:0 color subsampling.
(a)How many DCT’s are to be computed per frame? What is the maximum time to compute one DCT?
Answer: DCT/frame = 1440*1152/64*1.5 = 38880.
time/DCT = 1/(DCT/sec) = 1/(DCT/frame*frame/sec) = 0.86 microseconds
(b)Assume we are coding P frames. What is the maximum number of motion vectors per frame? What time is available to compute a motion vector?
Answer: MV/frame = 1440*1152/256 = 9720. time/MV = 1/(MV/sec) = 5.14 microseconds.
(c)What type of picture (I, P, B) places the greatest demand on motion vector computation?
Answer: B picture, since it requires 2 searches per macroblock.
Problem 7. Below we show two sets of equations for converting from RGB to YCbCr. Which set of equations is more appropriate for a computer? Which set of equations is more appropriate for RAC hardware implementation? Explain your recommendations.
Answer: The first formula requires 4 multiplications and 6 additions. The second formula requires 9 multiplications and 6 addtions. For a program, the first method is superior. For hardware implementation, the second method can be done with a RAC, while the first needs a network of adders and multipliers. The second method is easier to implement in hardware.
Problem 8. RACs, as described in Lecture 13, slide 25 (Chaper 10 in Bhaskaran and Konstantinides), can compute a DCT coefficient by evaluating 4 point vector dot products. Assume that the calculation is performed with 12 bit precision.
(a) Estimate the number of ROM bits required for each RAC.
Answer: Assume 12 bit words in ROM. There are 4 operands, so we will need 2^4 = 16 words. We require 12*16 = 196 bits.
(b) Suppose the functionality for the RAC is to be matched with a set of multipliers and adders. Parallel (array) multipliers will be used. How many multipliers would be required? Estimate the number of gates needed.
Answer: A flat-out parallel system would require 16 multipliers. Each multiplier would need about 12^2 adders, and each adder needs about 8 gates. The whole unit would need about 16*144*8 = 18432 gates.