Foundation of Video Coding

Generalized Lloyd Algorithm (LBG Algorithm)

• ©Yao Wang, 2003

• Coding: Quantization

• Start with initial codewords
• Iterate between finding best partition using NN condition, and updating codewords using centroid condition

Example

Rate-Distortion Characterization of Lossy Coding

• ©Yao Wang, 2003

• Coding: Quantization

• Operational rate-distortion function of a quantizer:
• Relates rate and distortion: R(D)
• A vector quantizer reaches different point on its R(D) curve by using different number of codewords
• Can also use distortion-rate function D(R)
• Rate distortion bound for a source
• Minimum rate R needed to describe the source with distortion <=D
• RD optimal quantizer:
• Minimize D for given R or vice versa

• Typical D(R) curve

Lossy Coding Bound (Shannon Lossy Coding Theorem)

• ©Yao Wang, 2003

• Coding: Quantization

• IN(F,G): mutual information between F and G, information provided by G about F
• QD,N: all coding schemes (or mappings q(g|f)) that satisfy distortion criterion dN(f,g)<=D

• h(F): differential entropy of source F
• RG(D): RD bound for Gaussian source with the same variance

RD Bound for Gaussian Source

• ©Yao Wang, 2003

• Coding: Quantization

• i.i.d. 1-D Gaussian:
• i.i.d. N-D Gaussian with independent components:
• N-D Gaussian with covariance matrix C:
• Gaussian source with power spectrum (FT of correlation function)