CS525 S2010 Hw3

Solution to Homework #3: Video Processing, DCT, and JPEG Encoding

Goal:

Learn basic video processing.

Learn Discrete Consine Transformation.

Learn JPEG entropy coding.

Assignment Date: 3/1/2010

Due Date: 3/8/2010

Related References:

Description:

Part1:

In year 2009, ATSC decides to start developing the next generation of HDTV standards with four times the resolution of today's HDTV system. Assume one simple solution is to increase the scanning lines from 1125 to 2250 and increase the BW 4 times, other paramters (CH, AR, FR, CV, Kf) not changed. What will be the RH and Rv numbers? What will be number of equivalent pixel in one frame? See pages 12 and 13 of video.pdf for the related formula.

Ans:
R_H=2*C_H*B_W/(A_R*N_L*F_R)=2*0.83*80000000/(1.78*2250*30)=1106.67
R_v=C_v*K_f*N_L=0.96*0.7*2250=1512
N_p=A_R*R_H*R_v=1.78*1106.67*1512=2,974,720

	NTSC	PAL	HDTV	hw3p1HTV
B_W	4.20	5.00	20.00	80.00
N_L	525.00	625.00	1125.00	2250.00
C_H	0.85	0.80	0.83	0.83
A_R	1.33	1.33	1.78	1.78
F_R	29.97	25.00	30.00	30.00
R_H	340.34	384.00	553.33	1106.67


Cv	0.92	0.92	0.96	0.96
N_L	525	625	1125	2250
Kf	0.7	0.7	0.7	0.7
Rv	338.1	402.5	756	1512


Np	153425.4	206080	743680	2974720

See the excel spreadsheet at http://cs.uccs.edu/~cs525/hw/solution/hw3/hw3p1q1.xls
You can use the spreadsheet in midterm to anwser the related questions.

What is the main difference between a composite TV system and a component TV system? (See Page 25 of video.pdf)

Ans: Component TV signal transmits the RGB signals separately. Therefore they are preserved better than the composite TV signal where the YIQ signal components are mixed and transmitted over a single channel.

The video standards converts RGB signal to YIQ signal format. how can we take advantage of the YIQ format, in terms of video compression utilizing the human perception system? (See Page 26 of video.pdf).

Ans: Since human eye is more sensitive to luminance than I signal (orange-cyan color), and least sensitive to Q signal (green-magenta color), we can use more bits to encode the Y (luminance) signal, fewer bits to I signal, and fewest bits to Q signal. Or we can dither the image plane of I signal and Q signal further so that fewer pixels (or equivalent of fewer bits are used to present them.)

Part2:

Blocking: The following are the 8x8 block data for a block in a Y plane. It has a black-white pattern.


hw3p2 =

     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0
    20    20    20    20    20    20    20    20
    20    20    20    20    20    20    20    20
     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0

Note that the above matrix can be created with

hw3p2=zeros(8,8); hw3p2([4 5],:)=20*ones(2,8)

Question A: Apply FDCT: What is the results 8x8 DCT coefficients, expressed in matrix form?
Note that you can run dctdemo.m for compute the dct coefficients:

enter the above statements to create hw3p2 matrix
enter getdctf(hw3p2) to display the 8x8 DCT coefficients.

Note that you can use format short e to see those small numbers.

Ans:

>> hw3p2=zeros(8,8); hw3p2([4 5],:)=20*ones(2,8)

hw3p2 =

     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0
    20    20    20    20    20    20    20    20
    20    20    20    20    20    20    20    20
     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0

>> getdctf(hw3p2)

ans =

   40.0000    0.0000   -0.0000    0.0000    0.0000    0.0000   -0.0000   -0.0000
    0.0000    0.0000    0.0000    0.0000    0.0000    0.0000    0.0000    0.0000
  -52.2625   -0.0000    0.0000   -0.0000    0.0000   -0.0000    0.0000    0.0000
   -0.0000    0.0000    0.0000    0.0000    0.0000    0.0000    0.0000    0.0000
   40.0000    0.0000   -0.0000    0.0000    0.0000    0.0000   -0.0000   -0.0000
    0.0000    0.0000    0.0000    0.0000    0.0000    0.0000    0.0000    0.0000
  -21.6478    0.0000    0.0000    0.0000    0.0000   -0.0000    0.0000    0.0000
    0.0000    0.0000    0.0000    0.0000    0.0000    0.0000    0.0000    0.0000

Threshold and quantization: Round the coefficients to the nearest integer numbers, given the above DCT matrix values.

ans =

   40    0   -0    0    0    0   -0   -0
    0    0    0    0    0    0    0    0
  -52   -0    0   -0    0   -0    0    0
   -0    0    0    0    0    0    0    0
   40    0   -0    0    0    0   -0   -0
    0    0    0    0    0    0    0    0
  -22    0    0    0    0   -0    0    0
    0    0    0    0    0    0    0    0

Question B: Zigzag sequence:Describe the order and content of the coefficients after arrange them in the zig-zag sequence.

40, two zeros, -52, six zeros, 40, ten zeros, -22, EOB

Question C: Run length and VLI Coding:Encode the intermediate sequence in (size, magnitude), (runlength, size, magnitude)+ symbol using runlength and VLI coding. Describe each data pattern of these fields in its equivalent decimal value.

Ans:
-52 --> (6, 63-52=11); -22 -->(5, 31-22=9)
(6, 40), (2, 6, 11), (6, 6, 40), (10, 5, 9), (0, 0)

Question D: How many bits will be used to encode the intermediate sequence?

Ans: Pattern:

Pattern:   (6, 40), (2, 6, 11), (6, 6, 40), (10, 5, 9), (0, 0)

# of bits:  4+  6+   4+ 4+  6+   4+ 4+  6+    4+ 4+  5+   4+ 4 = 59 bits.

Question E: Assume each of original source 8x8 block data is 8 bit, the runlength and size field are 4bits without using VLC Huffman coding, magnitude fields are encoded with VLI code. What is the compression ratio between the original data size and the encoded intermediate encoded sequence?

Ans: The original 8x8 block is encoced in 8*8*8=512 bits. The compression ratio 512/59=8.68:1.

Question F: If all elements of a JPEG block have the same non-zero value. How many zeros will appear in the transformed coefficients?

Ans: Only DC coefficient has non-zero value. Therefore there are 64-1=63 zeros.