Overview: motion-compensated coding

„ Motion-compensated prediction
„ Motion-compensated hybrid coding
„ Motion estimation by block-matching
„ Motion estimation with sub-pixel accuracy
„ Power spectral density of the motion-compensated
prediction error
„ Rate-distortion analysis
„ Loop filter
„ Motion compensated coding with sub-pixel accuracy
„ Rate-constrained motion estimation

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 1

 Motion-compensated prediction
previous frame
stationary Δt
background
current frame
x
time t
y
moving
object

⎛ dx ⎞
„Displacement vector“ ⎜ ⎟ shifted
⎝ dy ⎠ object

Prediction for the luminance signal S(x,y,t) within the moving object:

Sˆ(x, y,t) = S(x − d x , y − d y ,t − Δt)

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 2
Combining transform coding and prediction
Transform domain prediction Space domain prediction

T Q T T Q
- -
−1 −1
T T
T
PT T −1 PTS T

T −1 T −1

PT PS

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 3

 Motion-compensated hybrid coder

Coder
Control Control
Data
Intra-frame
DCT
DCT Coder
- Coefficients
Decoder Intra-frame
Decoder

0
Motion-
Compensated
Intra/Inter Predictor

Motion
Data
Motion
Estimator

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 4

 Motion-compensated hybrid decoder

Control
Data

DCT
Coefficients
Decoder Intra-frame
Decoder

0
Motion-
Compensated
Intra/Inter Predictor

Motion
Data

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 5

 Block-matching algorithm

search range in „ Subdivide current

reference frame frame into blocks.
Sk −1 „ Find one
displacement vector
for each block.
„ Within a search
range, find a best
„match“ that
minimizes an error
measure.
„ Intelligent search
strategies can
block of current reduce computation.
frame Sk

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 6

 Block-matching algorithm
Reference frame Current frame

Block is compared with a Block of pixels is considered

shifted array of pixels in the
reference frame to determine
the best match

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 7

 Block-matching algorithm
Reference frame Current frame

. . . process repeated for the next block

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 8

 Blockmatching: Matching Criterion

„ Sum of Squared Differences to determine similarity

Sum of all Current Reference
values in block
frame frame

∑
2
SSD(d x , d y ) = ⎡⎣ S k ( x, y ) − Sk −1 ( x + d x , y + d y ) ⎤⎦
x,y∈Block

Horizontal Vertical
shift shift

„ Alternative matching criteria: SAD (Sum of Absolute

Differences), cross correlation, . . .
„ Only integer pixel shifts (so far)

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 9

 Integer Pixel Shifts
Reference frame Current frame

Block is compared with a Block of pixels is considered

shifted array of pixels in the
reference frame to determine
the best match

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 10

 Integer Pixel Shifts
28 42 42 43 44 40 32 20 29 32 22

30 44 45 45 45 42 30 21 26 27 18

54 53 52 49 31 21
35 54 54 54
53 53
52
54 52
49
53
54 49
31
52
53 31
21
49
52 21
28
31
49 24
21
31 15
21

62 63 59 60 44 33
40 63 62 62
63 63
59
62 59
60
63
62 60
44
59
63 44
33
60
59 33
35
44
60 31
33
44 26
33

120 114 112 111 80 32

74 121 120 120
114 114
112
120 112
111
114
120 111
80
112
114 80
32
111
112 32
23
80
111 22
32
80 17
32

130 128 124 125 88 24

79 127 130 130
128 128
124
130 124
125
128
130 125
88
124
128 88
24
125
124 24
17
88
125 20
24
88 13
24

131 124 127 127 96 42

80 129 131 131
124 124
127
131 127
124
131 96
127
124 96
42
127 42
29
96
127 28
42
96 19
42

77 71 73 75 63 52
50 78 77 77
71 71
73
77 73
75
71
77 75
63
73
71 63
52
75
73 52
47
63
75 46
52
63 29
52

22 37 37 37 39 40 40 41 41 38 25

Block is compared with a Block of pixels is considered

shifted array of pixels in the
reference frame to determine
the best match

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 11

SSD Values Resulting from Blockmatching

1.6

SSD1.4
1.2

0.8

0.6

0.4
Estimated
Estimateddisplacement
displacement
0.2
Integer-pixel
Integer-pixelaccuracy
accuracy
0

0 14
12
5 10
10 8
6
Vertica 15 2 4
hift d x
l shift d n t al s
y Horizo

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 12

Motion-compensated prediction: example
Previous frame Current frame

Current frame with Motion-compensated

displacement vectors Prediction error
Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 13
 Interpolation of the SSD Minimum

SSD Sub-pixel
Accurate Fit parabola
Minimum through
3>3points
points
exactly
approximately

Horizontal shift dx

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 14

 2-d Interpolation of SSD Minimum

Paraboloid
SSD
„ Perfect fit through 6 points

„ Approximate fit through

>6 points

Ve
rtic
a ls
hif hi ft dx
td n t als
iz o
y
H or

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 15

 Blockmatching: search strategies I
Full search

„ All possible displacements • • • • • • • • • • • • •

• • • • • • • • • • • • •
within the search range are • • • • • • • • • • • • •
• • • • • • • • • • • • •
compared. • • • • • • • • • • • • •
„ Computationally expensive • • • • • • • • • • • • • dx
• • • • • • • • • • • • •
„ Highly regular, parallelizable • • • • • • • • • • • • •
• • • • • • • • • • • • •
• • • • • • • • • • • • •
• • • • • • • • • • • • •
• • • • • • • • • • • • •
• • • • • • • • • • • • •
dy

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 16

 Blockmatching: search strategies II
2D logarithmic search [Jain + Jain, 1981]

„ Iterative comparison of error •3 •5 •4 •5

measure values at 5 neighboring •5 •5 •5
•3 •2 •3 •4
points
•2 •1 •2
„ Logarithmic refinement of the dx
search pattern if •1 •1 •1
z best match is in the center of the 5- •1
point pattern
z center of search pattern touches
the border of the search range
dy

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 17

 Blockmatching: search strategies III
Diamond search [Li, Zeng, Liou, 1994] [Zhu, Ma, 1997]
dy

dx

Start with If best match If best match does not lie

large diamond lies in the center in the center of large
pattern at of large diamond, diamond, center large
(0,0) proceed with diamond pattern at new
small diamond best match

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 18

 Blockmatching: search strategies IV

Most search strategies can be further accelerated by . . .

„ Predictive motion search
z Use median of motion vectors in causal neighborhood as starting
point for search.
z Additionally test zero-vector as a starting point
„ Early termination
z Interrupt summation to calculate SSD or SAD, if value grows too
quickly (relative to previous best match)
z Stop search, if match is “good enough” (SSD, SAD < threshold)

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 19

 Block comparison speed-ups
„ Triangle and Cauchy-Schwarz inequality for SAD and SSE

∑ Sk − Sk −1 ≥ ∑ Sk − Sk −1 = ∑ Sk − ∑ Sk −1
block block block block
2 2
1⎛ ⎞ 1⎛ ⎞
∑ ( Sk − Sk −1 ) ∑ k k −1 ⎟⎠ N ⎜⎝ block
∑ k block
∑ k −1 ⎟⎠
2
≥ − = −
N ⎜⎝ block
S S S S
block

number of terms in sum

„ Strategy:
z Compute partial sums for blocks in current and previous frame
z Compare blocks based on partial sums
z Omit full block comparison, if partial sums indicate worse error measure
than previous best result
„ Performance: > 20x speed-up of full search block matching reported by
employing [Lin + Tai, IEEE Tr. Commun., May 97]
z Sum over 16x16 block
z Row wise block projection
z Column wise block projection
Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 20
 Hierarchical blockmatching
Displacement
vector field

Block
matching
current frame
previous frame

Filtering
and
Block subsampling
matching

Filtering
and
Block subsampling
matching

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 21

 Sub-pel accuracy
Displacement
vector field with
1/2-pel
accuracy

Block
matching

Displacement
vector field with Interpolation
integer-pel
accuracy

Block
matching
current frame
previousframe

Filtering
and
Block subsampling
matching

Filtering
and
Block subsampling
matching

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 22

 Sub-pel accuracy
„ Interpolate pixel raster of the reference frame to desired fractional pel
accuracy (e.g., by bi-linear interpolation)
„ Straightforward extension of displacement vector search to fractional
accuracy
„ Example: half-pel accurate displacements
• • • • • • • • • • • • •
• • • • • • • • • • • • •
• • • • • • • • • • • • •
• • • •
• • •• •• • • • • • • • • • • •
⎛ dx ⎞ ⎛ 4.5⎞
⎜ ⎟ =⎜ ⎟
• • •• •• • • • • • • • • • • •
• • •• •• • • • • • • • • • • •
• • • • • • • • • • • • • ⎝ dy ⎠ ⎝ 4.5⎠
• • • • • • • • • • • • •
• • • • • • • • • • • • •
• • • • • • • • • • • • •
• • • • • • • • • • • • •
• • • • • • • • • • • • •
• • • • • • • • • • • • •

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 23

 Bi-linear Interpolation

brightness

Interpolated
Pixel Value

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 24

 Bi-linear Interpolation (cont.)

I(x’,y’)

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 25

Model for performance analysis of an
MCP hybrid coder
luminance
signal S R-D optimal
e
intraframe
- encoder

intraframe
decoder

e‘

motion s‘
compensated
predictor

displacement estimate

⎛ dx ⎞ ⎛ Δ x ⎞
true displacement ⎜d ⎟ + ⎜Δ ⎟ displacement error
⎝ y⎠ ⎝ y⎠
Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 26
 Analysis of the motion-compensated prediction error

Motion-compensated signal
c ( x) = s ( x − Δx ) − n ( x)
Prediction error
Previous e ( x) = s ( x) − c ( x)
frame = s ( x) − s ( x − Δx ) + n ( x)

x
c(x) s(x)
Current
frame
Displacement dx Displacement error Δx

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 27

 Analysis of m.c. prediction error (cont.)

„ Motion-compensated prediction error

e( x) = s ( x) − c( x) = s ( x) − s ( x −Δx ) + n( x) = (δ ( x) −δ ( x −Δx ) ) ∗ s ( x) + n( x)
„ Power spectrum of prediction error, assuming constant displacement
error Δ x, statistical independence of s and n
( )( )
Φ ee (ω ) = Φ ss (ω ) 1 − e − jωΔ x 1 − e jωΔ x + Φ nn (ω )

( {
= 2Φ ss (ω ) 1 − Re e − jωΔ x }) + Φ nn (ω )

„ Random displacement error Δ x , statistically independent from s, n

{ ( { }) + Φ (ω )}
Φ ee (ω ) = E 2Φ ss (ω ) 1 − Re e − jωΔ x nn

= 2Φ ss (ω ) (1 − Re { E {e }}) + Φ (ω )
− jωΔ x
nn

= 2Φ ss (ω ) (1 − Re { P (ω )}) + Φ (ω ) nn

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 28

 Analysis of m.c. prediction error (cont.)

„ What is P(ω)? {
P ( ω ) = E e − jω Δ x }
∞
= ∫ { }
p Δ x ( Δ ) e − jω Δ d Δ = F p Δ x ( Δ x )
−∞

Fourier transform of the displacement error pdf!

„ Same as characteristic function of displacement error, except for sign

„ Extension to 2-d

( )
Φ ee (ω x , ω y ) = 2Φ ss (ω x , ω y ) 1 − Re { P(ω x , ω y )} + Φ nn (ω x , ω y )

Fourier transform of the noise spectrum

displacement error pdf
power spectrum of p(Δ x , Δ y )
luminance signal

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 29

Power spectrum of motion-compensated
prediction error

π
0
frequency ω x
Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 30
R-D function for MCP with integer-pixel accuracy
Minimum bit-rate for given SNR
„ (Δ x , Δ y ) assumed
T

uniformly distributed
between
1
Δ x = ± pel
2
1
Δ y = ± line ~0.7 bpp
2
„ Gaussian signal model 3
2 −
⎛ ωx +ω y ⎞ 2
2

Φ ss (ω x , ω y ) = A⎜ 1 +
⎝ ω 02 ⎟⎠
„ Typical parameters for CIF
resolution (352 x 288
pixels)

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 31

Required accuracy of motion compensation

„ p(Δ x , Δ y ) isotropic
Gaussian pdf with variance σ
2

3
−
⎛ ω +ω ⎞
2 2
2
Φss (ω x , ω y ) = A⎜1+
x y

ω02 ⎟⎠
„
⎝
„ Typical parameters for CIF
resolution (352 x 288 pixels)
„ Minimum bit-rate for
SNR = 30 dB

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 32

Model of MCP hybrid coder with loop filter
e R-D optimal
intraframe
luminance - encoder
signal S

intraframe
decoder

spatial
filter
F

motion
compensated
predictor
displacement estimate
⎛ dx ⎞ ⎛ Δ x ⎞
true displacement ⎜d ⎟ + ⎜Δ ⎟ displacement error
⎝ y⎠ ⎝ y⎠
Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 33
 Motion-compensated prediction error with loop filter

Motion-compensated signal Prediction error

c(x ) = s(x − Δ x ) − n(x ) e(x) = s(x) − f (x)∗ c(x)
= s(x) − f (x)∗ s(x − Δ x ) + f (x) ∗n(x)
Previous
frame Impulse response
of loop filter

x
c(x) s(x)
Current
frame
Displacement dx Displacement error Δx

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 34

 Spatial power spectrum of m.c. prediction error
with loop filter

Φee (Λ) = Φss (Λ) (1+ | F(Λ)|2 −2Re{ F(Λ)P(Λ)} ) +Φnn (Λ)| F(Λ)|2

P(Λ) 2 -D Fourier transform of displacement error pdf

F(Λ) 2 -D Fourier transform of f (x, y)
Φ uu spatial spectral power density of signal u
Λ vector of spatial frequencies (ω x , ω y )
n(x, y) noise

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 35

 Optimum loop filter

„ Wiener filter minimizes prediction error variance

∗ Φ ss (Λ )
Fopt (Λ ) = P (Λ ) ⋅
123 Φ (Λ ) + Φ (Λ )
1442443
ss nn

accounts for accuracy of accounts for noise

motion compensation

„ Resulting minimum prediction error spectrum

⎛ Φ ss (Λ ) ⎞
Φ ee (Λ ) = Φ ss (Λ ) ⎜1− | P(Λ ) |2
⎟
⎝ Φ ss (Λ ) + Φ nn (Λ ) ⎠

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 36

 Effect of loop filter

Moderately accurate Very accurate

motion compensation motion compensation

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 37

 Required accuracy of motion
compensation with loop filter
„ p(Δ x , Δ y ) isotropic Gaussian pdf with variance σ 2
„ Minimum bit-rate for SNR = 30 dB

~0.8 bpp

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 38

 Practical optimum loop filter design

„ Not practical for loop filter design

∗ Φ ss (Λ )
Fopt (Λ ) = P (Λ ) ⋅
123 Φ (Λ ) + Φ (Λ )
1442443
ss nn

Motion compensation “Noise” psd not known

accuracy not known
„ To determine Wiener filter from measurements:
cross spectrum between s(x,y) and
the motion-compensated signal
Φ sc (Λ) c(x, y) = r(x − dˆ x , y − dˆ y )
Fopt (Λ) =
Φ cc (Λ)

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 39

 Experimental evaluation of
fractional-pixel motion compensation
„ ITU-R 601 TV signals, 13.5 MHz sampling rate, interlaced,
blockwise motion compensation with blocksize16x16

Zoom Voiture

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 40

 Influence of noise on the
performance of MCP

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 41

Motion Compensation Performance in
H.263

500
Bit Rate [kbps]

400
Intra mode
300 only
Integer-pel
accuracy
200
1/2-pel
100 accuracy

0
24 30 36
Simulation details: PSNR [dB]
Foreman, QCIF, SKIP=2
Q=4,5,7,10,15,25

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 42

Rate-constrained motion estimation I

motion vector D
bit-rate R rate Rm

prediction error
rate Re

displacement error variance

∂D ∂D
optimum trade-off: =
∂Rm ∂Re

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 43

 Rate-constrained motion estimation II

„ How to find best motion vector subject to rate constraint?

„ Lagrangian cost function: solve unconstrained problem
rather than constrained problem

min(D + λRm )

error measure motion vector rate

⇒ Interpret motion search as ECVQ problem.

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 44

 Rate-constrained Motion Estimation
in H.263 Reference Model TMN-10
40 20
TMN-10,
38 TMN-10, w/ rate-constrained

Partial bit-rate [kbps]

w/ rate-constrained motion estimation
36 motion estimation 15
PSNR [dB]

34
TMN-10, 10
32 w/o rate-constrained
motion estimation (TMN-9) TMN-10,
30 w/o rate-constrained
5 motion estimation (TMN-9)

28

26 0
0 50 100 150 200 0 50 100 150 200
Bit Rate [kbps] Bit Rate [kbps]
Simulation details:
Foreman, QCIF, SKIP=2
Q=4,5,7,10,15,25
Annexes D+F

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 45

 Video coder control

„ Encoding decisions Coder

Control
Control
Data
z Coding modes
(intra/inter/motion comp.)
z Block size Intraframe DCT

z Motion vectors Input

- DCT Coder Coefficients

Video Decoder
z Quantizer step size Intraframe
Decoder
z Suppression of DCT coefficients
„ Solution
z Embed rate-constrained motion 0
estimation into mode decision Motion-
Compensated
with Lagrangian cost function Predictor
Intra/Inter
z Couple Lagrange multiplier to
quantizer step size Motion
„ Difficulties Data

z Joint entropy coding of side

information
z Temporal dependencies due to
DPCM structure

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 46

 History of motion-compensated coding

Complexity
• Intraframe coding: only spatial correlation exploited
Î DCT [Ahmed, Natarajan, Rao 1974], JPEG [1992] increases
• Conditional replenishment
Î H.120 [1984] (DPCM, scalar quantization)
• Frame difference coding
Î H.120 Version 2 [1988]
• Motion compensation: integer-pel accurate displacements
Î H.261 [1991]
• Half-pel accurate motion compensation
Î MPEG-1 [1993], MPEG-2/H.262 [1994]
• Variable block-size motion compensation
Î H.263 [1996], MPEG-4 [1999]

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 47

 Efficiency of motion-compensated coding

PSNR Half-pel Frame

TMN-10 motion difference
[dB]
Variable compensation coding Foreman
block size (MPEG-1 1993) (H.120 1988)
10 Hz, QCIF
motion
compensation
100 frames encoded
38
(H.263 1998)
36
67 %
34
Intraframe
32 DCT coding
(DCT 1974,
30 Integer-pel JPEG 1992)
motion
28 compensation
(H.261 1991)
26 Bit-Rate [kbps]
0 100 200 300 400 500

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 48

 Efficiency of motion-compensated coding

PSNR Variable
[dB] block size
motion Conditional Mother & Daughter
42 compensation Replenishment
10 Hz, QCIF
(H.263 1996) (H.120)
40 100 frames encoded

38

36

34 Intraframe
DCT coding
32 (JPEG)
60 %
30
Bit-Rate [kbps]
28
0 100 200 300 400

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 49

 Efficiency of motion-compensated coding

PSNR
[dB]
40 Mobile & Calendar
Variable
38 block size 10 Hz, QCIF
motion 35 % 100 frames encoded
36 compensation 40 %
34 (H.263 1996)

32
30
Intraframe
28 DCT coding
Integer-pel (JPEG)
26 motion
compensation
24 (H.261 1991)
Bit-Rate [kbps]
22
0 500 1000 1500

Bernd Girod: EE398B Image Communication II Motion Compensated Coding no. 50