Transform Coding in Practice

Last Lecture

Last Lectures: Basic Concept Transform Coding

Transform reduces linear dependencies (correlation) between samples before scalar quantization
For correlated sources: Scalar quantization in transform domain is more efficient

encoder decoder
u0 q0 q0 u00
α0 β0
forward entropy entropy inverse
s u1 q1 b q1 u10 s0
transform α1 coding decoding β1 transform
.. ..
A . γ γ −1 . 0
A−1
uN−1 qN−1 qN−1 uN−1
αN−1 βN−1

Encoder (block-wise) Decoder (block-wise)

Forward transform: u =A·s Entropy decoding: {qk } = γ −1 (b)
Scalar quantization: qk = αk (uk ) Inverse quantization: uk0 = βk (qk )
Entropy coding: b = γ( {qk } ) Inverse transform: s 0 = A−1 · u 0
Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 2 / 50
Last Lecture

Last Lectures: Orthogonal Block Transforms

Transform matrix has property: A−1 = AT (special case of unitary matrix: A−1 = (A∗ )T )
b0
   

 b1 





A = b2 
A −1 T
 b 0 b 1 b 2 · · · b N−1
= A = 
..
  
   
 .   
b N−1

Basis vectors bk (rows of A, columns of A−1 = AT ) form an orthonormal basis

Geometric interpretation: Rotation (and potential reflection) in N-dimensional signal space

Why Orthogonal Transforms ?

Same MSE distortion in sample and transform space: ||u 0 − u||22 = ||s 0 − s||22
Minimum MSE in signal space can be achieved by
minimization of MSE for each individual transform coefficient
Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 3 / 50
Last Lecture

Last Lectures: Bit Allocation and High-Rate Approximations

Bit Allocation of Transform Coefficients

Optimal bit allocation: Pareto condition
∂
Dk (Rk ) = −λ = const =⇒ high rates: Dk (Rk ) = const
∂Rk

High-Rate Approximation
High-rate distortion rate function for transform coding with optimal bit allocation
Y N1 Y N1
D(R) = ε̃2 · σ̃ 2 · 2−2R with ε̃2 = ε2k , σ̃ 2 = σk2
k k

High-rate transform coding gain GT and energy compaction measure GEC

1
PN−1 2
DSQ (R) ε2S · σS2 σS2 σ
GT = = 2 2, GEC = 2 = qQk=0 k
N
DTC (R) ε̃ · σ̃ σ̃ N N−1 2
k=0 σk
Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 4 / 50
Last Lecture

Last Lectures: Karhunen Loève Transform (KLT)

Design criterion: Orthogonal transform A that yields uncorrelated transform coefficients

σ02
 
0 ··· 0
 0 σ12 ··· 0 
CUU = A · CSS · AT =  CSS · b k = σk2 · b k
 
.. .. .. ..  =⇒
.
 
 . . . 
2
0 0 ··· σN−1

Eigenvector equation for all basis vectors b k (rows of transform matrix A)

Rows of KLT matrix A are the unit-norm eigenvectors of CSS

Transform coefficient variances σk2 are the eigenvalues of CSS
b0 σ02 0 ··· 0
   

 b1 

 0
 σ12 ··· 0 

A= ..  C UU = 
 .. .. .. ..

.
  
 .   . . . 
2
b N−1 0 0 ··· σN−1

Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 5 / 50
Last Lecture

Last Lectures: Maximum Energy Compaction and Optimality

High-Rate Approximation for KLT and Gauss-Markov

High-rate operational distortion-rate function
N−1
DN (R) = ε2 · σS2 · (1 − %2 ) N · 2−2R

High-rate transform coding gain: Increases with transform size N

1−N 1
GTN = GEC
N
= (1 − %2 ) N =⇒ GT∞ =
1 − %2

For N → ∞, gap to fundamental lower bound reduces to space-filling gain (1.53 dB)

On Optimality of KLT
KLT yields uncorrelated transform coefficients and maximizes energy compaction GEC
KLT is the optimal transform for stationary Gaussian sources
Other sources: Optimal transform is hard to find (iterative algorithm)
Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 6 / 50
Signal-Independent Unitary Transforms

Transform Selection in Practice

Optimal Unitary Transform

Stationary Gaussian sources: KLT
General sources: Not straightforward to determine (typically KLT close to optimal)
Signal dependent (may change due to signal instationarities)

Adaptive Transform Selection

Determine transform in encoder, include transform specification in bitstream
Increased side information may lead to sub-optimal overall coding efficiency
Simple variant: Switched transforms (e.g., in H.266/VVC)

Signal-Independent Transforms
Choose transform that provides good performance for variety of signals
Not optimal, but often close to optimal for typical signal
Most often used design in practice
Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 7 / 50
Signal-Independent Unitary Transforms / Walsh-Hadamard Transform

Walsh-Hadamard Transform

For transform sizes N that are positive integer powers of 2

 
1 AN/2 AN/2
h i
AN = √ with A1 = 1 .
2 AN/2 −AN/2

Examples: Transform matrices for N = 2, N = 4, and N = 8

 
1
  1 1 1 1 1 1 1 1
1 1
A2 = √  1 −1 1 −1 1 −1 1 −1 
2 1 −1  

 1 1 −1 −1 1 1 −1 −1 

  1  1 −1 −1 1 1 −1 −1 1 
1 1 1 1 A8 = √  
1  8 1 1 1 1 −1 −1 −1 −1 
1 −1 1 −1   
A4 = √    1 −1 1 −1 −1 1 −1 1 
4 1 1 −1 −1   
 1 1 −1 −1 −1 −1 1 1 
1 −1 −1 1
1 −1 −1 1 −1 1 1 −1

Very simple orthogonal transform (only additions, subtractions, and final scaling)
Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 8 / 50
Signal-Independent Unitary Transforms / Walsh-Hadamard Transform

Basis Functions of the WHT (Example for N = 8)

b0 b4

b1 b5

b2 b6

b3 b7

Media coding: Walsh-Hadamard transform with strong quantization

Piece-wise constant basis vectors yield subjectively disturbing artifacts

Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 9 / 50
Signal-Independent Unitary Transforms / Fourier Transform

Discrete Version of the Fourier Transform

The Fourier Transform

Fundamental transform used in mathematics, physics, signal processing, communications, ...
Integral transform representing signal as integral of frequency components
Forward and inverse transform are given by
Z∞ Z∞
X (f ) = F x(t) = x(t) · e −2πift dt −1
x(t) = X (f ) · e 2πift df
 
⇐⇒ x(t) = F
−∞ −∞

Basis functions are complex exponentials bf (t) = e 2πift

Discrete Version of the Fourier Transform

Fourier transform for finite discrete signals
Could also be useful for coding of discrete signals
Can be derived using sampling and windowing
Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 10 / 50
Signal-Independent Unitary Transforms / Fourier Transform

Important Properties of the Fourier Transform

n o
Linearity: F a · h(t) + b · g (t) = a · H(f ) + b · G (f )
 
n o 1 f
Scaling: F h(a · t) = ·H
|a| a
n o
Translation: F h(t − t0 ) = e −2πit0 f · H(f )
n o
Modulation: F e 2πitf0 · h(t) = H(f − f0 )
n o
Duality: F H(t) = h(−f )

n o Z ∞ 
Convolution: F h(t) ∗ g (t) = F g (τ ) h(t − τ ) dτ = H(f ) · G (f )
−∞
n o
Multiplication: F h(t) · g (t) = H(f ) ∗ G (f )
Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 11 / 50
Signal-Independent Unitary Transforms / Fourier Transform

The Dirac Delta Function

Dirac Delta Function
Not a function in traditional sense Dirac delta distribution
Can be thought of function with the following properties
 Z∞
+∞ : x = 0
δ(x) = and δ(x) dx = 1
0 : x 6= 0
−∞

Important Properties Z ∞
Sifting: h(t) δ(t − t0 ) dt = h(t0 )
−∞
Z ∞
Convolution: h(t) ∗ δ(t − t0 ) = h(τ ) δ(t − t0 − τ ) dτ = h(t − t0 )
−∞

∞ ∞
!
Z ∞ X X
Sampling: h(t) δ(t − k · t0 ) dt = h(k · t0 )
−∞ k=−∞ k=−∞
Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 12 / 50
Signal-Independent Unitary Transforms / Fourier Transform

Selected Fourier Transform Pairs

Dirac delta function δ(t − T ) complex exponential


F δ(t − T )

t f
x(t) = δ(t − T ) X (f ) = e −2πifT = cos(2πfT ) + i sin(2πfT )

Dirac comb шT (t) Dirac comb ШT (f )

1
T T

∞ t ∞ f
X X
шT (t) = δ(t − kT ) ШT (f ) = δ(f − k/T )
k=−∞ k=−∞

Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 13 / 50
Signal-Independent Unitary Transforms / Fourier Transform

Selected Fourier Transform Pairs

rectangular window Sinc filter


rectT (t) F rectT (f )

T
2
T
t f
1 : |t| ≤ T /2

 1
rectT (t) = F rectT (f ) = sin(πfT ) = T sinc(fT )
0 : |t| > T /2 πf

Gaussian g (t) Gaussian G (f )

t f
−π·t 2 1 2
g (t) = e with σt2 = G (f ) = e −π·f = g (f )
2π

Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 14 / 50
Signal-Independent Unitary Transforms / Discrete Fourier Transform

Derivation of Discrete Fourier Transform: (1) Sampling of Signal

continuous signal s(t) Fourier transform S(f )

t f
× (multiplication) ∗ (convolution)

Dirac comb ш0 (t) Dirac comb Ш0 (f )

t f
= =
sampled signal s(t) ш0 (t) Fourier transform S(f )∗Ш0 (f )

t f
Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 15 / 50
Signal-Independent Unitary Transforms / Discrete Fourier Transform

Derivation of Discrete Fourier Transform: (2) Time Restriction

sampled signal s(t) ш0 (t) Fourier transform S(f )∗Ш0 (f )

t f
× (multiplication) ∗ (convolution)

rectangular window r (t) Sinc filter R(f )

t f
= =
finite sampled signal s(t) ш0 (t) r (t) Fourier transform S(f )∗Ш0 (f )∗R(f )

t f
Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 16 / 50
Signal-Independent Unitary Transforms / Discrete Fourier Transform

Derivation of Discrete Fourier Transform: (3) Sampling of Spectrum

finite sampled signal s(t) ш0 (t) r (t) Fourier transform S(f )∗Ш0 (f )∗R(f )

t f
∗ (convolution) × (multiplication)

Dirac comb ш1 (t) Dirac comb Ш1 (f )

t f
= =
periodic sampled signal s(t) ш0 (t) r (t) ∗ ш1 (t)
 
Fourier transform [S(f )∗Ш0 (f )∗R(f )] Ш1 (f )

t f
Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 17 / 50
Signal-Independent Unitary Transforms / Discrete Fourier Transform

The Discrete Fourier Transform

periodic sampled signal sper (t) Fourier transform Sper (f )

t f

N samples are represented by N complex Fourier coefficients

Discrete Fourier Transform

Forward and inverse transform are given by
N−1 N−1
1 X 2πkn 1 X 2πkn
u[k] = √ s[n] · e −i N and s[n] = √ u[k] · e i N
N n=0 N k=0

Unitary transform that produces complex transform coefficients

Basis vectors are sampled complex exponentials
Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 18 / 50
Signal-Independent Unitary Transforms / Discrete Fourier Transform

Complex Basis Functions of the DFT (Example for N = 8)

   
1 2πk 1 2πk 1 2πk
bk [n] = √ e i N n = √ cos n + i · √ sin n = rk [n] + i · ik [n]
N N N N N

=(b0) = 0 =(b4) = 0
r0 i0 r4 i4

b5 = b3∗
r1 i1 r5 i5

b6 = b2∗
r2 i2 r6 i6

b7 = b1∗
r3 i3 r7 i7

Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 19 / 50
Signal-Independent Unitary Transforms / Discrete Fourier Transform

Complex Basis Functions of the DFT (Example for N = 8)

   
1 2πk 1 2πk 1 2πk
bk [n] = √ e i N n = √ cos n + i · √ sin n = rk [n] + i · ik [n]
N N N N N

DFT for Real Signals

r0 r4
Symmetry of complex coefficients
u[k] = u ∗ [N − k]
r1 i1 Vanishing imaginary parts
k ∈ 0, N2 : = u[k] = 0
 

r2 i2
N real samples are mapped to
N real coefficients

r3 i3 Fast algorithm:
Fast Fourier transform (FFT)
Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 20 / 50
Signal-Independent Unitary Transforms / Discrete Fourier Transform

Disadvantage of DFT for Transform Coding

discrete signal sper (t) transform coefficients Sper (f )

t f
N samples N coefficients

Sampling of frequency spectrum causes implicit periodic signal extension

Often: Large differences between left and right signal boundary

Large difference reduces rate of convergence of Fourier series

Strong quantization yields significant high-frequency artefacts

Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 21 / 50
Signal-Independent Unitary Transforms / Discrete Trigonometric Transforms

Overcome DFT Disadvantage: Discrete Cosine Transform

DFT:

implicit signal replica signal implicit signal replica

DCT: DFT

implicit signal replica signal mirrored signal implicit signal replica

Idea of Discrete Cosine Transform (DCT)

Introduce mirror symmetry (different possibilities)
Apply DFT of approximately double size (or four times the size)
No discontinuities in periodic signal extension
Ensure symmetry around zero: Only cosine terms
Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 22 / 50
Signal-Independent Unitary Transforms / Discrete Trigonometric Transforms

Discrete Trigonometric Transforms (DTTs)

Discrete Cosine Transforms (DCTs)

Introduce mirror symmetry around zero and apply DFT of larger size
Imaginary sine terms get eliminated
Only cosine terms remain
8 possibilities: DCT-I to DCT-VIII
2 cases for left side: Whole sample or half-sample symmetry
4 cases for right side: Whole sample or half-sample symmetry or anti-symmetry
Most relevant case: DCT-II (half-sample symmetry at both sides)

Discrete Sine Transforms (DSTs)

Introduce anti-symmetry around zero and apply DFT of larger size
Real cosine terms get eliminated
Only imaginary sine terms remain
Similarly as for DCT: 8 possibilities (DST-I to DST-VIII)
Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 23 / 50
Signal-Independent Unitary Transforms / Discrete Trigonometric Transforms

The Discrete Cosine Transform (DCT) Family

DCT-I DFT of size 2N − 2 DCT-V DFT of size 2N − 1

DCT-II DFT of size 2N DCT-VI DFT of size 2N − 1

DCT-III DFT of size 4N DCT-VII DFT of size 4N − 2

DCT-IV DFT of size 4N DCT-VIII DFT of size 4N + 2

Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 24 / 50
Signal-Independent Unitary Transforms / Discrete Trigonometric Transforms

The Discrete Sine Transform (DST) Family

DST-I DFT of size 2N + 2 DST-V DFT of size 2N + 1

DST-II DFT of size 2N DST-VI DFT of size 2N + 1

DST-III DFT of size 4N DST-VII DFT of size 4N + 2

DST-IV DFT of size 4N DST-VIII DFT of size 4N − 2

Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 25 / 50
Signal-Independent Unitary Transforms / Discrete Cosine Transform of Type II

Derivation of the Discrete Cosine Transform of Type II (DCT-II)

DFT

implicit signal replica signal mirrored signal implicit signal replica

Signal for applying the DFT

Given: Discrete signal s[n] of size N (i.e., 0 ≤ n < N)
Mirror signal with sample repetition at both sides (size 2N)
(
m s[n] : 0≤n<N
s [n] =
s[2N − n − 1] : N ≤ n < 2N
Ensure symmetry around zero by adding half-sample shift
(
s[n − 1/2] : 0≤n<N
s + [n] = s m [n − 1/2] =
s[2N − n − 3/2] : N ≤ n < 2N

Apply DFT of size 2N to new signal s + [n]

Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 26 / 50
Signal-Independent Unitary Transforms / Discrete Cosine Transform of Type II

Derivation of the Discrete Cosine Transform of Type II (DCT-II)

s[n − 1/2] : 0≤n<N


s + [n] =
s[2N − n − 3/2] : N ≤ n < 2N

(2N)−1  
1 2πkn s + only known at half-sample
s + [n] · e −i (2N)
X
DFT of size 2N : u + [k] = p
(2N) n=0 positions → use m = n − 1/2

2N−1  
1 X + 1 1
· e −i N (m+ 2 )
πk
= √ s m+
2N m=0 2
N−1 2N−1
!
1 X
−i πk 1
N (n+ 2 )
X 1
N (m+ 2 )
−i πk
= √ s[n] · e + s[2N − m − 1] · e
2N n=0 m=N

yn=2N−m−1
N−1 N−1
!
1 X
−i πk ( n+ 12 )+
X
−i πk 2N−n− 21
( )
= √ s[n] · e N s[n] · e N

2N n=0 n=0
Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 27 / 50
Signal-Independent Unitary Transforms / Discrete Cosine Transform of Type II

Derivation of the Discrete Cosine Transform of Type II (DCT-II)

Continue derivation
N−1 N−1
!
+ 1 X
−i πk 1
N (n+ 2 )
X
−i πk 1
N (2N−n− 2 )
u [k] = √ s[n] · e + s[n] · e
2N n=0 n=0

N−1 N−1
!
1 X
−i πk 1
N (n+ 2 )
X
−i2πk i πk 1
N (n+ 2 )
= √ s[n] · e + s[n] · |e {z } · e
2N n=0 n=0 1

N−1
1 X  πk 1 1

s[n] · e −i N (n+ 2 ) + e i N (n+ 2 )
πk
= √
2N n=0 | {z }
1
2 cos( πk
N (n+ 2 ))

DFT of extended signal

r N−1   
2 X π 1
u + [k] = · s[n] · cos k n+
N n=0 N 2

Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 28 / 50
Signal-Independent Unitary Transforms / Discrete Cosine Transform of Type II

Derivation of the Discrete Cosine Transform of Type II (DCT-II)

DFT of extended signal (2N real samples) has 2N real transform coefficients
r N−1   
+ 2 X π 1
k = 0, . . . , 2N − 1 : u [k] = · s[n] · cos k n+
N n=0 N 2

1 Signal s[n] is completely described by first N transform coefficients

r N−1   
2 X π 1
k = 0, . . . , N − 1 : u + [k] = · s[n] · cos k n+
N n=0 N 2

2 Basis functions of derived transform are orthogonal to each other, but don’t have the same norm
Introduce factors αk so that transform matrix becomes orthogonal
N−1   
X π 1
k = 0, . . . , N − 1 : u[k] = αk · s[n] · cos k n+
n=0
N 2

Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 29 / 50
Signal-Independent Unitary Transforms / Discrete Cosine Transform of Type II

Discrete Cosine Transform of Type II (DCT-II)

Specification of DCT-II
Forward transform (DCT-II) and inverse transform (IDCT-II) are given by

N−1    N−1   
X π 1 X π 1
u[k] = αk s[n] · cos k n+ and s[n] = αk · u[k] · cos k n+
n=0
N 2 N 2
k=0

with scaling factors

(p
1/N : k = 0
αk = p
2/N : k 6= 0

The orthogonal transform matrix A = {akn } has the elements

  
π 1
akn = αk · cos k n+
N 2

Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 30 / 50
Signal-Independent Unitary Transforms / Discrete Cosine Transform of Type II

Comparions of DFT and DCT-II Basis Functions (Example for N = 8)

  
1 2πk π 1
DFT: bk [n] = √ e i N n = rk [n] + i · ik [n] DCT-II: bk [n] = αk · cos k n+
N N 2

r0 r4 b0 b1

r1 i1 b2 b3

r2 i2 b4 b5

r3 i3 b6 b7

Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 31 / 50
Signal-Independent Unitary Transforms / Discrete Cosine Transform of Type II

Image & Video Coding: 2D Transforms

Separable Transforms
Successive 1D transforms of rows and columns of image block
Separable forward and inverse transforms

u = A · s · BT and s = AT · u · B

with s — N ×M block of image samples

A — N ×N transform matrix (typically DCT-II)
B — M ×M transform matrix (typically DCT-II)
u — N ×M block of transform coefficients

Great practical importance:

Two matrix multiplications of size N ×N instead of
one multiplication of a vector of size 1×N 2 with a matrix of size N 2 ×N 2
Complexity reduction from O(N 4 ) to O(N 3 ) [ also fast algorithms for DCT-II ]
Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 32 / 50
Signal-Independent Unitary Transforms / Discrete Cosine Transform of Type II

Example: Basis Images of Separable 8×8 DCT-II

Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 33 / 50
Signal-Independent Unitary Transforms / Discrete Cosine Transform of Type II

Example: Separable DCT-II for 8×8 Image Block

Forward transform for 8 × 8 block of samples: u = A · s · AT

horizontal vertical
DCT DCT

original block after 2d DCT

Example calculation of 2d DCT-II:

1 Horizontal DCT of input block: u ∗ = s · AT
2 Vertical DCT of intermediate result: u = A · u ∗ = A · s · AT

Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 34 / 50
Signal-Independent Unitary Transforms / Discrete Cosine Transform of Type II

Practical Importance of DCT-II

Justification for usage of DCT-II

Represents signal as weighted sum of frequency components
Similar to KLT for highly correlated sources (% → 1)
Independent of source characteristics
Fast algorithms for computing forward and inverse transform

DCT-II of size 8×8 is used in

Image coding standard: JPEG
Video coding standards: H.261, H.262/MPEG-2, H.263, MPEG-4 Visual

Integer approximation of DCT-II is used in

Video coding standard H.264/AVC (4×4 and 8×8)
Video coding standard H.265/HEVC (4×4, 8×8, 16×16, 32×32)
New standardization project H.266/VVC (from 4×4 to 64×64, including non-square blocks)
Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 35 / 50
Transform Coding in Practice / Typical Design

Transform Coding in Practice

Orthogonal Transform
Typically: DCT-II or integer approximation thereof (separable transform for blocks)
Potential extension in H.266/VVC:
Switched transform of DCT/DST families (DCT-II, DST-VII, ...)
Non-separable transforms

Scalar Quantization
Uniform reconstruction quantizers (or very similar designs)
Bit allocation by using same quantization step size for all coefficients
Usage of advanced quantization algorithms in encoder
May use quantization weighting matrices for perceptual optimization

Entropy Coding of Quantization Indexes

Zig-zag scan (or similar scan) for 2D transforms
Simple: Run-level coding, run-level-last coding, or similar approach
Better coding efficiency: Adaptive arithmetic coding
Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 36 / 50
Transform Coding in Practice / Typical Design

Bit Allocation in Practice (for Uniform Reconstruction Quantizers)

Remember: Optimal bit allocation: Pareto condition

∂Dk (Rk )
= const
∂Rk
Pareto condition for high rates
Dk = ε2k · σk2 · 2−2Rk =⇒ Dk (Rk ) = const
High rate distortion approximation for URQs
1 2
Dk = ∆
12 k
Quantization step sizes for optimal bit allocation at high rates
1 2
Dk = ∆ = const =⇒ ∆k = const = ∆
12 k

In practice, (nearly) optimal bit allocation is typically achieved

by using the same quantization step size ∆ for all transform coefficients
Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 37 / 50
Transform Coding in Practice / Color Transformation

Color Transform for Image & Video Coding

RGB Color Transform for Compression
YCbCr
Many versions (also depends on RGB color space)
Example: RGB → YCbCr transform used in JPEG
     
Y 0.2990 0.5870 0.1140 R
 Cb −128  =  −0.1687 −0.3313 0.5000  ·  G 
Cr −128 0.5000 −0.4187 −0.0813 B
     
R 1 0 1.4020 Y
 G  =  1 −0.3441 −0.7141  ·  Cb −128 
B 1 1.7720 0 Cr −128

Energy Compaction for Example Image

2 = 3862.28
σR 2 = 3099.67
σY
2
σG = 4250.44 2 =
σCb 83.94
2
σB = 5869.39 2 =
σCr 70.10

Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 38 / 50
Transform Coding in Practice / Color Transformation

The YCbCr Chroma Sampling Format

Human being are less sensitive to color differences (at same luminance)
In most applications: Color difference components are downsampled

RGB YCbCr 4:4:4 YCbCr 4:2:0

color transform downsampling

most common
format in
image coding

Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 39 / 50
Transform Coding in Practice / Image Compression Example: JPEG

The Image Compression Standard JPEG

Partition color components (Y, Cb, Cr) into blocks of 8 × 8 samples

Y Cb Cr

Transform coding of 8 × 8 blocks of samples

block of 2D scalar entropy

samples transform quantization coding

sequence
of bits
reconstructed 2D inverse decoder entropy
block transform mapping decoding

Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 40 / 50
Transform Coding in Practice / Image Compression Example: JPEG

JPEG: Transform of Sample Blocks

Separable DCT-II of size 8×8 (fast implementation possible)
Forward transform (in encoder)

horizontal vertical
DCT DCT

original block after 2d DCT

Inverse transform (in decoder)

horizontal vertical
IDCT IDCT

reconstructed block rec. transform coeffs.

Effect of transform: Compaction of signal energy (for typical blocks)

Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 41 / 50
Transform Coding in Practice / Image Compression Example: JPEG

JPEG: Quantization
u−4 u−3 u−2 u−1 u0 u1 u2 u3 u4 u5
0 0 0 0 0
s−5 s−4 s−3 s−2 s−1 s00 s10 s20 s30 s40 s50
∆ ∆

−5∆ −4∆ −3∆ −2∆ −1∆ 0 1∆ 2∆ 3∆ 4∆ 5∆ s

Uniform Reconstruction Quantizers

Equally spaced reconstruction levels (indicated by step size ∆)
Simple decoder mapping
t0 = ∆ · q
Simplest (but not best) encoder:
q = round(t/∆)
Better encoders use Lagrangian optimization (minimization of D + λR)
Quantization step size ∆ determines tradeoff between quality and bit rate
Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 42 / 50
Transform Coding in Practice / Image Compression Example: JPEG

JPEG: Entropy Coding

0.242 0.108 0.053 0.009

0.105 0.053 0.022 0.002

0.046 0.017 0.006 0.001

0.009 0.002 0.001 0.000

probabilities P(qk 6= 0) zig-zag scan (JPEG)

1 Scanning of Quantization indexes

Convert matrix of quantization indexes into sequence
Traverse quantization indexes from low to high frequency positions
JPEG: Zig-zag scan

Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 43 / 50
Transform Coding in Practice / Image Compression Example: JPEG

JPEG: Entropy Coding

2 Entropy Coding of Sequences of Quantization Indexes

Often long sequences of zeros (in particular at end of sequence)
Entropy coding should exploit this property

JPEG: Run-Level Coding (V2V code)

Map sequence a symbols (transform coefficients) into (run,level) pairs,
including a special end-of-block (eob) symbol
level : value of next non-zero symbol
run : number of zero symbols that precede next non-zero symbol
eob : all following symbols are equal to zero (end-of-block)
Assign codewords to (run,level) pairs (including eob symbol)

Example: 64 symbols: 5 3 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 ...

(run,level) pairs: (0,5) (0,3) (3,1) (1,1) (2,1) (eob)
Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 44 / 50
Transform Coding in Practice / Image Compression Example: JPEG

JPEG Compression Example

Original
Lossy Compressed:
Image (960×720
JPEG image
(Quality
points,
94)RGB: 2 MByte)
66)
27)
6) 18.60
3.88 %
1.85
0.49 %

25.8
54.0
204
5.4 : 1

100 %

Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 45 / 50
Transform Coding in Practice / Image Compression Example: JPEG

JPEG Compression Example

Original
Lossy Compressed:
Image (960×720
JPEG image
(Quality
points,
94)RGB: 2 MByte)
66)
27)
6) 18.60
3.88 %
1.85
0.49 %

25.8
54.0
204
5.4 : 1

100 %

Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 45 / 50
Transform Coding in Practice / Image Compression Example: JPEG

JPEG Compression Example

Original
Lossy Compressed:
Image (960×720
JPEG image
(Quality
points,
94)RGB: 2 MByte)
66)
27)
6) 18.60
3.88 %
1.85
0.49 %

25.8
54.0
204
5.4 : 1

100 %

Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 45 / 50
Transform Coding in Practice / Image Compression Example: JPEG

JPEG Compression Example

Original
Lossy Compressed:
Image (960×720
JPEG image
(Quality
points,
94)RGB: 2 MByte)
66)
27)
6) 18.60
3.88 %
1.85
0.49 %

25.8
54.0
204
5.4 : 1

100 %

Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 45 / 50
Transform Coding in Practice / Image Compression Example: JPEG

JPEG Compression Example

Original
Lossy Compressed:
Image (960×720
JPEG image
(Quality
points,
94)RGB: 2 MByte)
66)
27)
6) 18.60
3.88 %
1.85
0.49 %

25.8
54.0
204
5.4 : 1

100 %

Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 45 / 50
Transform Coding in Practice / Audio Compression Example: AAC

Audio Compression Example: MPEG-2 Advanced Audio Coding (AAC)

Main Component: Transform Coding of Sample Blocks
Transform: Modified DCT for overlapping blocks
Quantization: Scalar quantization with psycho-acoustic model
Entropy Coding: Variant of Huffman coding

Linear Transform
Audio signal is coded based on overlapping blocks of samples
Transform: Modified discrete cosine transform (MDCT)

Quantization of Transform Coefficients

Scalar quantization of transform coefficients (spectral coefficients)
Utilization of psycho-acoustic models by noise shaping

Entropy Coding of Quantization Indexes

Grouping and interleaving
Huffman coding for tuples of n quantization indexes (n is variable)
Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 46 / 50
Transform Coding in Practice / Audio Compression Example: AAC

Modified Discrete Cosine Transform (MDCT)

Forward Transform (MDCT)

The forward transform maps 2N samples to N transform coefficients
2N−1    
1 X π N +1 1
u[k] = √ s[n] · cos n+ k+
N n=0 N 2 2

Inverse Transform (IMDCT)

The inverse transform maps N transform coefficients to 2N samples
N−1    
1 X π N +1 1
x[n] = √ u[k] · cos n+ k+
N k=0 N 2 2

Perfect Reconstruction
Neighboring blocks of samples s[n] overlap by 50% (at each side)
Perfect reconstruction of s[n] is achieved by adding the inverse transformed blocks x[n]
Property of time-domain aliasing cancellation
Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 47 / 50
Summary

Summary of Lecture

Signal-Independent Transforms
Walsh-Hadamard Transform (WHT): Perceptual disturbing artefacts
Discrete Fourier Transform (DFT): Problem due to implicit periodic signal extension
Discrete Trigonometric Transforms: Family of Sine and Cosine transforms

Discrete Cosine Transform of Type II (DCT-II)

DFT of mirrored signal with half-sample symmetry at both sides
Reduced blocking artifacts compared to DFT
Good approximation of KLT for highly-correlated signals

Transform Coding in Practice

Color transforms in image and video coding: RGB to YCbCr conversion
JPEG image compression: 2D DCT-II + URQ + Run-level coding
AAC audio compression: MDCT for overlapped blocks + scalar quantization + Huffman coding
Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 48 / 50
Exercises

Exercise 1: Correlation of Transform Coefficients

Given is a zero-mean AR(1) sources with a variance σ 2 and a correlation coefficient % = 0.9

Consider transform coding of blocks of 2 samples using the transform

     
uk,0 1 1 1 s2k
=√ · ,
uk,1 2 −1 1 s2k+1
where k represents the index of the transform block
Determine the following variances and covariances of the transform coefficients
(inside a block and between neighbouring blocks):
 2
E Uk,0 =? E{ Uk,0 Uk+1,0 } = ?
 2
E Uk,1 = ? E{ Uk,1 Uk+1,1 } = ?
E{ Uk,0 Uk,1 } = ? E{ Uk,0 Uk+1,1 } = ?

Is it worth to exploit the correlations between the transform coefficients of neighboring block
(e.g., for typical correlation factors of % ≈ 0.9) ?
Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 49 / 50
Exercises

Exercise 2: First Version of Lossy Image Codec (Implementation)

Implement a first lossy image codec for PPM images:
1 Use the source code of last weeks exercise as basis (see KVV)
2 Add some variant of entropy coding for the quantization indexes, for example:
Simple Rice coding or Exp-Golomb coding (see lossless codec example in KVV)
Adaptive binary arithmetic coding using a unary binarization (see lossless coding example in KVV)
...
3 Implement an encoder that converts a PPM image into a bitstream file
4 Implement a corresponding decoder that converts a bitstream file into a PPM image
5 Test your encoder with some example images and multiple quantization step sizes
6 (Optional) Try to improve your codec by using the YCbCr color format
Implement an RBG-to-YCbCr transform before the actual encoding
Implement the inverse YCbCr-to-RGB transform after the actual decoding
Possible extension: Sub-sampling of chroma components
Heiko Schwarz (Freie Universität Berlin) — Data Compression: Transform Coding in Practice 50 / 50