Motion estimation for video compression
Blockmatching
Search strategies for block matching
Block comparison speedups
Hierarchical blockmatching
Sub-pixel accuracy
Bernd Girod: EE398A Image and Video Compression
Motion estimation no. 1
Block-matching algorithm
search range in
previous frame
Sk 1
Subdivide current frame into blocks.
Find one displacement vector for each block.
Within a search range, nd a best match that minimizes an error measure.
Intelligent search strategies can reduce computation.
block of current
frame
Sk
Bernd Girod: EE398A Image and Video Compression
Motion estimation no. 2
Block-matching algorithm
Previous Frame
Current Frame
Measurement window is compared with a shifted block of pixels in the other image, to determine the best match
Block of pixels is selected as a measurement window
Bernd Girod: EE398A Image and Video Compression
Motion estimation no. 3
Block-matching algorithm
Previous Frame
Current Frame
. . . process repeated for another block.
Bernd Girod: EE398A Image and Video Compression
Motion estimation no. 4
Blockmatching: Matching Criterion
Sum of Squared Differences to determine similarity
Sum all values in measurement window
Current image
Previous image
Horizontal shift
Vertical shift
Alternative matching criteria: SAD (Sum of Absolute Differences), cross correlation, . . .
How about sub-pixel shifts?
Bernd Girod: EE398A Image and Video Compression
Motion estimation no. 5
SSD Values Resulting from Blockmatching
SSD
Estimated displacement
Integer-pixel accuracy
-8
Vertica l
-3
shift d
-6
td al shif x nt Horizo
-4
-2
Motion estimation no. 6
Bernd Girod: EE398A Image and Video Compression
Motion-compensated prediction: example
Previous frame
Current frame
Prediction with
displacement vectors
Motion-compensated
Prediction error
Motion estimation no. 7
Bernd Girod: EE398A Image and Video Compression
Interpolation of the SSD Minimum
SSD
Sub-pixel
Accurate
Minimum
Fit parabola parabola through
through 3 points
>3 points
exactly
approximately
Horizontal shift dx
Bernd Girod: EE398A Image and Video Compression
Motion estimation no. 8
2-d Interpolation of SSD Minimum
Paraboloid
Perfect t through 6 points
Approximate t through >6 points
SSD
on oriz
ta
ift l sh
dx
Bernd Girod: EE398A Image and Video Compression
Motion estimation no. 9
Blockmatching: search strategies I
Full search
All possible displacements within the search range are compared.
Computationally expensive
Highly regular, parallelizable
Bernd Girod: EE398A Image and Video Compression
Motion estimation no. 10
Blockmatching: search strategies II
2D logarithmic search [Jain + Jain, 1981]
Iterative comparison of error measure values at 5 neighboring points
Logarithmic renement of the search pattern if
best match is in the center of the 5point pattern
center of search pattern touches the border of the search range
Bernd Girod: EE398A Image and Video Compression
Motion estimation no. 11
Blockmatching: search strategies III
Diamond search [Li, Zeng, Liou, 1994] [Zhu, Ma, 1997]
Start with large diamond pattern at
(0,0)
If best match lies in the center of large diamond, proceed with small diamond
If best match does not lie in the center of large diamond, center large
diamond pattern at new best match
Bernd Girod: EE398A Image and Video Compression
Motion estimation no. 12
Blockmatching: search strategies IV
Most search strategies can be further accelerated by . . .
Predictive motion search
Use median of motion vectors in causal neighborhood as starting point for search.
Additionally test zero-vector as a starting point
Interrupt summation to calculate SSD or SAD, if value grows too quickly (relative to previous best match)
Stop search, if match is good enough (SSD, SAD < threshold)
Early termination
Bernd Girod: EE398A Image and Video Compression
Motion estimation no. 13
Block comparison speed-ups
Triangle and Cauchy-Schwarz inequalities for SAD and SSE
block
S
k
Sk 1
block
Sk 1 =
2
block
S S
k block
k 1
2
block
(S
S k 1
1 1 S k S k 1 = S k S k 1 N block N block block
Strategy:
number of terms in sum
Compute partial sums for blocks in current and previous frame
Compare blocks based on partial sums
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]
Sum over 16x16 block
Row wise block projection
Column wise block projection
Motion estimation no. 14
Bernd Girod: EE398A Image and Video Compression
Hierarchical blockmatching
Integer-pixel accuracy Extension to sub-pixel accuracy
Bernd Girod: EE398A Image and Video Compression
Motion estimation no. 15
Sub-pixel accuracy
Interpolate pixel raster of the reference image to desired sub-pixel accuracy (typically by bi-linear interpolation)
Straightforward extension of displacement vector search to fractional accuracy
Example: half-pixel accurate displacements
Motion estimation no. 16
Bernd Girod: EE398A Image and Video Compression
Bi-linear Interpolation
brightness
Interpolated Pixel Value
Bernd Girod: EE398A Image and Video Compression
Motion estimation no. 17
Reading
J. R. Jain, A. K. Jain, Displacement Measurement and Its Application in Interframe Image Coding, IEEE Trans. Communications, vol. COM-29, no. 12, pp. 1799-1808, Dec. 1981.
Y.-C. Lin, S.-C. Tai, Fast Full-Search Block-Matching Algorithm for Motion-Compensated Video Compression, IEEE Trans. Communications, vol. 45, no. 5, pp. 527-531, May 1997.
Bernd Girod: EE398A Image and Video Compression
Motion estimation no. 18
