Foundation of Video Coding

Function Representation

• ©Yao Wang, 2003

• Coding: Quantization

Distortion Measure

• ©Yao Wang, 2003

• Coding: Quantization

• General measure:

• Mean Square Error (MSE)

Uniform Quantization

• ©Yao Wang, 2003

• Coding: Quantization

• Uniform source:

• Each additional bit provides 6dB gain!

Minimum MSE (MMSE) Quantizer

• ©Yao Wang, 2003

• Coding: Quantization

• Nearest neighbor condition:
• Centroid condition:
• Special case: uniform source
• MSE optimal quantizer = Uniform quantizer

• (Nearest Neighbor
• Condition)

• (Centroid Condition)

• or

High Resolution Approximation

• ©Yao Wang, 2003

• Coding: Quantization

• For a source with arbitrary pdf, when the rate is high so that the pdf within each partition region can be approximated as flat:

Lloyd Algorithm

• Iterative algorithms for determining MMSE quantizer parameters
• Can be based on a pdf or training data
• Iterate between centroid condition and nearest neighbor condition

Vector Quantization

• ©Yao Wang, 2003

• Coding: Quantization

• General description
• Nearest neighbor quantizer
• MMSE quantizer
• Generalized Lloyd algorithm

Vector Quantization: General Description

• ©Yao Wang, 2003

• Coding: Quantization

• Motivation: quantize a group of samples (a vector) together, to exploit the correlation between these samples
• Each sample vector is replaced by one of representative vectors (or patterns) that often occur in the signal
• Applications:
• Color quantization: Quantize all colors appearing in an image to L colors for display on a monitor that can only display L distinct colors at a time – Adaptive palette
• Image quantization: Quantize every NxN block into one of the L typical patterns (obtained through training). More efficient with larger block size, but block size are limited by complexity.