ECE-C 490 Image Processing Architectures
Practice Final
Winter 2002-3
Do any six (6, VI, 203) problemsAll problems have the same weight
Please keep your answers short and to the point.
Problem 1. A source has three symbols: a, b, c, with probabilities p(a) = 0.95, p(b) = 0.025, p(c) = 0.025
(a)Estimate the average number of bits required to code each of the symbols with an optimal code.
Answer: The best code requires –log2p bits per symbol. The a would require 0.074 bits, while the b and c would require about 5,32 bits each
(b)Assume that we encode a sequence of 100 symbols from this source with an arithmetic code. Estimate the number of code bits required.
Answer: When things work well, the arithmetic code need H = 0.336 bits per symbol, so that 100 symbols would need 34 bits.
Problem 2. A source produces symbols (integers) over the range -128 to 127. All values have equal probability.
(a)How many bits are needed to code symbols from the source? Use a lossless code.
Answer: There are 256 symbols. We need 8 bits.
(b) We are allowed to use a maximum of 3 bits per symbol. Describe a lossy coding method that achieves this goal.
Answer: For 3 bits, there will be 8 levels. 256/step = 8. Quantize, with a step of 32.
(c) Estimate the RMS error produced by the method in part (b).
Answer: N = 32/sqrt(12) = 9.24.
Problem 3. Assume we have a subroutine that performs n-point DCT transforms. We measure its speed and find that for n = 8 the computation time is 8 microseconds, and for n = 16 the time is 18 microseconds.
(a)Find the time for computing 8x8 and 16x16 2D DCTs.
Answer: To perform an NxN 2D DCT we need to do 2N 1D DCT’s. The 8x8 DCT requires 16*8 = 128 microseconds. The 16x16 DCT requires 18*32 = 576 microseconds.
(b)Will 16x16 point DCT processing of an image be faster or slower than 8x8 processing? By what percentage?
Answer: The 8x8 DCT requires 128/64 = 2 microseconds per pixel. The 16x16 DCT needs 576/256 = 2.25 microseconds per pixel. The larger DCT is slower by 0.25/2 = 12.5%.
Problem 4.
(a) In an MPEG-1 picture, luminance and chrominance are processed differently. How many luminance pixels are coded in a SIF? How many chrominance pixels?
Answer: Luminence is full resolution, 352x288 = 101,376. Chrominance is sumbsampled by a factor of 2 in both directions, but there are two frames, leading to 50,688 pix per frame
(b) What is the main difference between MPEG-2 4:2:0 and 4:2:2 profiles? What is the intended application of each?
Answer: The main differences are that (1) 4:2:2 is allocated more bits and (2) chrominance is subsampled by a factor of 2 in the horizontal direction only. 4:2:2 is intended for professional (pre-production) use.
Problem 5.
(a)Compare MPEG-1 and H.261 standards. What are the intended applications of these standards? Describe some similarities and differences.
Answer: MPEG-1 was intended for digital movies on CD. H.261 was intended for teleconferencing. The SIF and CIF for the two standards were similar, similar frame predictive coding was used. MPEG-1 allowed I, P, and B pictures, while H.261 used only I and P pictures.
(b)Is H.263 more similar to MPEG-2 or to MPEG-4? Explain your answer.
Answer: H.263 was designed for lower bit rates. MPEG-2 was designed for higher quality. MPEG-4 was designed for lower bit rates. H.263 is closer to MPEG-4 than to MPEG-2.
Problem 6. A video is coded with an IPBBPBBPBBPBBP picture sequence. The average compression is 8 for I pictures, 25 for P pictures, and 100 for B pictures.
(a) What is the average compression?
Answer: 1 I picture, 5 P pictures, 8 B pictures. Compression is 14/(1/8+5/25+8/100) = 34.6
(b) Is the second P picture in the group based on the I picture, the first P picture, or one of the B pictures? Explain.
Answer: P pictures are based on previous P or I pictures, whichever is closer. The second P picture is based on the first P picture.
Problem 7. According to Table 8.1, DCT processing for H.261 (CIF at 30 fps) requires 60 MOPS.
(a) Estimate the computational requirements for DCT processing at QCIF and sub-QCIF picture format. State your assumptions.
Answer: Assume that the processing is proportional to the number of pixels per second. Assume that QCIF and sub-QCIF are all at 30 fps. The DCT processing is then proportional to pixels per picture.
CIF / QCIF / Sub-QCIFH pix / 352 / 176 / 128
V pix / 288 / 144 / 96
Pix/(Y frame) / 101376 / 25344 / 12288
Est comp (MOPS) / 60 / 15 / 7.27
(b) The H.261 CIF picture format is very similar to the MPEG SIF format. Do you expect that, at the same RMS noise level, the compression for H.261 will be the same as for MPEG-1? Explain.
Answer: MPEG uses B pictures and fractional pixel accuracy motion vectors. Both features produce greater compression at the same accuracy. Therefore MPEG should produce better compression at the same RMS noise level.
Problem 8.
(a) Teleconferencing standards (H.261 and H.263) use only I and P pictures (no B pictures). Why?
Answer: Delay between transmission and reception has to be kept to a minimum in teleconferencing. B pictures introduce delay, because they are processed after the succeeding P pictures.
(b) Which of the two standards is designed to operate at lower bitrates? Name at least one feature that was used to make this possible.
Answer: H.263 is designed for lower bitrates. This is enabled by the QCIF and QCIF formats, lower frame rates, and refinements in coding such as half-pixel accuracy in motion vectors, differential coding of motion vectors, etc.
Problem 9.
(a) Estimate the storage requirement, in megabytes, for a 120 minute film with (1) MPEG-1, and (2) MPEG-2 at Main level and Main profile.
Answer: MPEG-1 is nominally 1.5 Mbit/sec, so that the film requires 10.8 Gbit (1.35 Gbyte). MPEG-2 at Main level and Main profile requires a (maximum) of 15 Mbit/sec, of 100.8 Gbit (13.5 Gbyte)
(a) According to Table 8.1, motion estimation for H.261 (CIF at 30 fps) requires 608 MOPS. Assume that the same software subroutines are used for motion estimation in MPEG-1. Estimate the processing requirements. Explain your calculation.
Answer: Assume MPEG-1 operating at SIF (352x250, 30 fps). CIF is 352x288. Assume that computing load is proportional to pixels per second. This leads ot a load of
608*(352*250*30)/(352*288*30) = 528 GOP.
This is an under-estimate, since MPEG uses a larger search range.