Foundation of Video Coding

VQ as Space Partition

• ©Yao Wang, 2003

• Coding: Quantization

• Every point in a region (Bl) is replaced by (quantized to) the point indicated by the circle (gl)

Distortion Measure

• ©Yao Wang, 2003

• Coding: Quantization

• General measure:

• MSE:

Nearest Neighbor (NN) Quantizer

• ©Yao Wang, 2003

• Coding: Quantization

• Challenge: How to determine the codebook?

Complexity of NN VQ

• ©Yao Wang, 2003

• Coding: Quantization

• Complexity analysis:
• Must compare the input vector with all the codewords
• Each comparison takes N operations
• Need L=2^{NR} comparisons
• Total operation = N 2^{NR}
• Total storage space = N 2^{NR}
• Both computation and storage requirement increases exponentially with N!
• Example:
• N=4x4 pixels, R=1 bpp: 16x2^16=2^20=1 Million operation/vector
• Apply to video frames, 720x480 pels/frame, 30 fps: 2^20*(720x480/16)*30=6.8 E+11 operations/s !
• When applied to image, block size is typically limited to <= 4x4
• Fast algorithms:
• Structured codebook so that one can conduct binary tree search
• Product VQ: can search subvectors separately

MMSE Vector Quantizer

• ©Yao Wang, 2003

• Coding: Quantization

• Necessary conditions for MMSE
• Nearest neighbor condition
• Generalized centroid condition:
• MSE as distortion:

Caveats 

• ©Yao Wang, 2003

• Coding: Quantization

• Both quantizer satisfy the NN and centroid condition, but the quantizer on the right is better!
• NN and centroid conditions are necessary but NOT sufficient for MSE optimality!