Predictive Coding

Prediction

Prediction in Images

Principle of Differential Pulse Code Modulation
(DPCM)

DPCM and entropy-constrained scalar
quantization

DPCM and transmission errors

Adaptive intra-interframe DPCM

Conditional Replenishment
Thomas Wiegand: Digital Image Communication Predictive Coding - 1
 Prediction
Prediction is difficult – especially for the future.
Mark Twain

Prediction: Statistical estimation procedure where
future random variables are estimated/predicted from
past and present observable random variables.

Prediction from previous samples: Sˆ 0 = f (S1,S2 ,...,SN ) = f (S)

Optimization criterion
E = {( S 0
Sˆ0 ) 2 } = E{[ S 0
f ( S1 , S 2 ,..., S N )]2 }  min

Optimum predictor:
Sˆ0 = E{S 0 | ( S1 , S 2 ,...S N )}

Thomas Wiegand: Digital Image Communication Predictive Coding - 2

 Structure

The optimum predictor Sˆ0 = E{S 0 | ( S1 , S 2 ,...S N )}
can be stored in a table (Pixels: 8 bit  size 28N)

Optimal linear prediction (zero mean, Gaussian RVs)
Sˆ = a S + a S + ... + a S = a t S
0 1 1 2 2 N N

Optimization criterion
E{( S 0
Sˆ0 ) 2 } = E{( S 0
a t S) 2 }

Optimum linear predictor is solution of
a t R S = E{S 0S t }

In case RS=E{SSt} is invertible

a = R
S1 E{S 0S}
Thomas Wiegand: Digital Image Communication Predictive Coding - 3
 Prediction in Images: Intra-frame Prediction

Past and present observable random variables are
prior scanned pixels within that image

When scanning from upper left corner to lower right
corner:
B C D

A X

1-D Horizontal prediction: A only

1-D Vertical prediction: C only

Improvements for 2-D approaches (requires line store)
P2 Q
sˆ( x, y ) = 
p =  P1 q = 0
a ( p, q )  s ( x  p, y  q )
1 424 3
( p ,q )
( 0, 0 )
Thomas Wiegand: Digital Image Communication Predictive Coding - 4
 Prediction Example: Test Pattern

s[x,y] uH[x,y]=
s[x,y]-0.95 s[x-1,y]

uV[x,y]= uD[x,y]=s[x,y]-
0.5(s[x,y-1]+ s[x-1,y])
s[x,y]-0.95 s[x,y-1]

Thomas Wiegand: Digital Image Communication Predictive Coding - 5

 Prediction Example: Cameraman

s[x,y] uH[x,y]=
s[x,y]-0.95 s[x-1,y]

uV[x,y]= uD[x,y]=s[x,y]-
s[x,y]-0.95 s[x,y-1] 0.5(s[x,y-1]+ s[x-1,y])

Thomas Wiegand: Digital Image Communication Predictive Coding - 6

 Change of Histograms: Cameraman
Image signal Prediction error
signal (diag. pred.)
3000 4
x 10
2500 2

2000 1.5

1500
1
1000
0.5
500

0 0
0 50 100 150 200 250 -50 0 50

Can we use prediction for compression ?

Yes, if we reproduce the prediction signal at the decoder
Thomas Wiegand: Digital Image Communication Predictive Coding - 7
 Differential Pulse Code Modulation
Coder
e e' entropy
input s quantizer
coder
-

ŝ s' channel
predictor

Decoder
+ e' entropy
output s '
decoder
+
predictor ŝ
Reconstruction error =
Prediction error Reconstruction quantization error
e = s
sˆ s ' = e'+ sˆ s '
s = e'
e = q

Thomas Wiegand: Digital Image Communication Predictive Coding - 8

 DPCM and Quantization

Prediction is based on quantized samples

Stability problems for large quantization errors

Prediction shapes error signal (typical pdfs: Laplacian,
generalized Gaussian)

Simple and efficient: combine with entropy-
constrained scalar quantization

Higher gains: Combine with block entropy coding

Use a switched predictor
• Forward adaptation (side information)
• Backward adaptation (error resilience, accuracy)

DPCM can also be conducted for vectors
• Predict vectors (with side information)
• Quantize prediction error vectors
Thomas Wiegand: Digital Image Communication Predictive Coding - 9
 Comparison for Gauss-Markov Source:
=0.9

SNR [dB]
35

2
= 10 log10
D 30

25

Linear predictor order
N=1, a=0.9 20

Entropy-Constrained
15 R(D*),
=0.9
Scalar Quantizer with
Huffman VLC DPCM & ECSQ

Iterative design 10 Panter & Dite App
algorithm applied Entropy-Constrained Opt.
5
R [bits]
0
0 1 2 3 4 5 6 7

Thomas Wiegand: Digital Image Communication Predictive Coding - 10

 DPCM with Entropy-Constrained Scalar Quantization

Example: Lena, 8 b/p

K=511, H=4.79 b/p K=15, H=1.98 b/p K=3, H=0.88 b/p

K...number of reconstruction levels, H...entropy
from: Ohm

Thomas Wiegand: Digital Image Communication Predictive Coding - 11

 Transmission Errors in a DPCM System

For a linear DPCM decoder, the transmission error
response is superimposed to the reconstructed signal
S'

For a stable DPCM decoder, the transmission error

response decays

Finite word-length effects in the decoder can lead to

residual errors that do not decay (e.g., limit cycles)

from: Girod

Thomas Wiegand: Digital Image Communication Predictive Coding - 12

 Transmission Errors in a DPCM System II

Example: Lena, 3 b/p (fixed code word length)

Error rate p=10-3.

1D pred., hor. aH=0.95 1D pred., ver. aV=0.95 2D pred.*,aH=aV=0. 5
from: Ohm

Thomas Wiegand: Digital Image Communication Predictive Coding - 13

 Inter-frame Coding of Video Signals

Inter-frame coding exploits:
• Similarity of temporally successive pictures

• Temporal properties of human vision

Important inter-frame coding methods:

• Adaptive intra/inter-frame coding
• Conditional replenishment
• Motion-compensating prediction (in Hybrid Video Coding)
• Motion-compensating interpolation

from: Girod

Thomas Wiegand: Digital Image Communication Predictive Coding - 14

Principle of Adaptive Intra/Inter-Frame DPCM
Predictor is switched between two states:
for moving or changed areas.

Intra-frame prediction Inter-frame prediction (previous frame

for moving or changed areas. prediction) for still areas of the picture.

s S 22 S 23 S 24
S 22 S 23 S 24 4 0m
S2 S3 S4

S2 S3 S4
S 21 S 20 S 25
S 21 S 20 S 25
S1 S0 FRAME N - 1
FRAME N - 1
FRAME N S1 S0

FRAME N

Sˆ = a1
S1 '+ a2
S 2 '+ a3
S3 '+ a4
S 4 ' Sˆinter = S '20 from: Girod

Thomas Wiegand: Digital Image Communication Predictive Coding - 15

 Intra/Inter-Frame DPCM: Adaptation Strategies, I

Feedforward Adaptation
s + e e' e' s'
Quantizer VLC VLC
ŝ -
ŝ ŝ
inter Interframe
ŝinter Interframe
s' predictor
predictor
Intraframe
Intraframe predictor
ŝintrapredictor ŝintra

Predictor
adaptation
Intra/inter-frame
Switching
information

Coder Decoder
from: Girod

Thomas Wiegand: Digital Image Communication Predictive Coding - 16

 Intra/Inter-Frame DPCM: Adaptation Strategies, II

Feedback Adaptation

s + e e' e' s'

Quantizer VLC VLC
-
ŝ
ŝ
ŝinter ŝinter
Inter-frame
Inter-frame predictor
predictor s' Intra-frame
Intra-frame ŝintra predictor
ŝintra predictor
Predictor
Predictor adaptation
adaptation

Coder Decoder

from: Girod

Thomas Wiegand: Digital Image Communication Predictive Coding - 17

 Principle of a Conditional Replenishment Coder

TRANSMISSION SIGNAL
SIGNAL
CODING, BUFFERING, OUTPUT
CHANNEL
INPUT ADDRESSING, DECODING,
BUFFERING ADDRESSING
SEGMENTER
(MOVEMENT
DETECTOR)

FRAME DELAY FRAME DELAY

(1 PICTURE MEMORY) (1 PICTURE MEMORY)

Coder Decoder

Still areas: repeat from frame store

Moving areas: transmit address and waveform
from: Girod

Thomas Wiegand: Digital Image Communication Predictive Coding - 18

 Change Detection
Example of a pel-oriented change detector
Current
frame

+ Average Eliminate isolated

ABS of 3x3 points or pairs of
window Threshold points
Decision
- changed/
Previous unchanged
frame
Example of a block-oriented change detector

Current
frame
+
Accumulate
ABS over NxN
blocks Threshold Decision
- changed/
Previous
frame unchanged
from: Girod

Thomas Wiegand: Digital Image Communication Predictive Coding - 19

 The "Dirty Window" Effect
Conditional replenishment scheme with change detection threshold
set too high leads to the subjective impression of looking through a
dirty window.

Moving Background
Area
picked up Moving areas
by change missed by
detector change detector

from: Girod

Thomas Wiegand: Digital Image Communication Predictive Coding - 20

 Summary

Prediction: Estimation of random variable from past or
present observable random variables

Optimal prediction

Optimal linear prediction

Prediction in images: 1-D vs. 2-D prediction

DPCM: Prediction from previously coded/transmitted
samples (known at coder and decoder)

DPCM and quantization

DPCM and transmission errors

Adaptive Intra/Inter-frame DPCM: forward adaptation
vs. backward adaptation

Conditional Replenishment: Only changed areas of
image are transmitted
Thomas Wiegand: Digital Image Communication Predictive Coding - 21