Motion Estimation for Video Coding - Stanford University

1 Motion Estimation for Video Coding Motion -Compensated Prediction Bit Allocation Motion Models Motion Estimation Efficiency of Motion Compensation Techniques T. Wiegand / B. Girod: EE398A Image and Video Compression Motion Estimation no. 1. Hybrid Video Encoder Coder Control Control Data s[ x, y, t ] u[ x, y, t ] Intra-Frame DCT. DCT Coder - Coefficients Decoder Intra-Frame Decoder u '[ x, y, t ]. s ' [ x, y , t ]. 0. Motion - Compensated Intra/Inter Predictor s [ x, y, t ] Motion Data Motion Estimator T. Wiegand / B. Girod: EE398A Image and Video Compression Motion Estimation no. 2. Motion -Compensated Prediction Previous Stationary frame background Moving t object Current frame x y time t dx . Displaced d object y . 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 ).

2 T. Wiegand / B. Girod: EE398A Image and Video Compression Motion Estimation no. 3. Motion -Compensated Prediction: Example Frame 1 s[x,y,t-1] (previous) Frame 2 s[x,y,t] (current) Partition of frame 2 into blocks (schematic). Size of Blocks Accuracy of Motion Vectors Referenced blocks in frame 1 Frame 2 with Difference between Motion - displacement vectors compensated prediction and current frame u[x,y,t]. T. Wiegand / B. Girod: EE398A Image and Video Compression Motion Estimation no. 4. Motion Models Motion in 3-D space corresponds to displacements in the image plane Motion compensation in the image plane is conducted to provide a prediction signal for efficient Video compression Efficient Motion -compensated prediction often uses side information to transmit the displacements Displacements must be efficiently represented for Video compression Motion models relate 3-D Motion to displacements assuming reasonable restrictions of the Motion and objects in the 3-D world Motion Model d x x x f x (a, x, y ), d y y y f y (b, x, y ).

3 X, y : location in previous image x , y : location in current image a, b : vector of Motion coefficients dx , d y : displacements T. Wiegand / B. Girod: EE398A Image and Video Compression Motion Estimation no. 5. Representation of Video Signal Decoded Video signal is given as s [ x, y, t ] s [ x, y, t ] u [ x, y, t ]. Motion -compensated Prediction residual signal prediction signal M 1. s [ x, y, t ] s ( x d x , y d y , t t ) u ( x, y ) c j j ( x, y). j 0. N 1 N 1. d x ai i ( x, y), d y bi i ( x, y). i 0 i 0. Transmitted residual parameters Transmitted Motion parameters Ru f (c), c (c0 ,..). Rm f (a, b), a (a0 ,..), b (b0 ,..). T. Wiegand / B. Girod: EE398A Image and Video Compression Motion Estimation no. 6. Rate-Constrained Motion Estimation Bit-rate Motion vector rate D.

4 Rm Prediction error rate Ru Displacement error variance dD dD. Optimum trade-off: , R Rm Ru dRm dRu Displacement error variance can be influenced via Block-size, quantization of Motion parameters Choice of Motion model T. Wiegand / B. Girod: EE398A Image and Video Compression Motion Estimation no. 7. Lagrangian Optimization in Video Coding A number of interactions are often neglected Temporal dependency due to DPCM loop Spatial dependency of Coding decisions Conditional entropy Coding Rate-Constrained Motion Estimation [Sullivan, Baker 1991]: min Dm m Rm Distortion after Lagrange Number of bits Motion compensation parameter for Motion vector Rate-Constrained Mode Decision [Wiegand, et al. 1996]: min D R. Distortion after Lagrange Number of bits reconstruction parameter for Coding mode T.

5 Wiegand / B. Girod: EE398A Image and Video Compression Motion Estimation no. 8. Motion Models N 1 N 1. d x ai i ( x, y), d y bi i ( x, y). i 0 i 0. Translational Motion model d x a0 , d y b0. 4-Parameter Motion model: translation, zoom (isotropic Scaling), rotation in image plane d x a 0 a1 x a 2 y d y b 0 a 2 x a1 y Affine Motion model: d x a 0 a1 x a 2 y d y b 0 b1 x b 2 y Parabolic Motion model d x a 0 a1 x a 3 y a 2 x 2 a 6 y 2 a 5 xy d x b 0 b1 x b3 y b 2 x 2 b 6 y 2 b5 xy T. Wiegand / B. Girod: EE398A Image and Video Compression Motion Estimation no. 9. Impact of the Affine parameters 150. d x a0 translation 100. 50. y 0. -150 -100 -50 0 50 100 150. -50. -100. -150. x 150 150. 100 100. 50. d x a1 x scaling 50. y 0. y 0. -150 -100 -50 0 50 100 150 -150 -100 -50 0 50 100 150.

6 -50 -50. -100 -100. -150 -150. x x 150. 100. d x a3 y sheering 50. y 0. -150 -100 -50 0 50 100 150. -50. -100. -150. x T. Wiegand / B. Girod: EE398A Image and Video Compression Motion Estimation no. 10. Impact of the Parabolic parameters 150. d x a2 x 100. 2. 50. y 0. -150 -100 -50 0 50 100 150. -50. -100. -150. x 150 150. d x a6 y 100 100. 2. 50 50. y 0. y 0. -150 -100 -50 0 50 100 150 -150 -100 -50 0 50 100 150. -50 -50. -100 -100. -150 -150. x x 150. 100. d x a5 xy 50. y 0. -150 -100 -50 0 50 100 150. -50. -100. -150. x T. Wiegand / B. Girod: EE398A Image and Video Compression Motion Estimation no. 11. Differential Motion Estimation Assume small displacements dx,dy: u ( x, y, t ) s( x, y, t ) s ( x, y, t , d x , d y ). s ( x, y, t t ) s ( x, y, t t ).

7 S( x, y, t ) s ( x, y, t t ) dx dy x y Displace frame difference Horizontal and vertical gradient of image signal S. Aperture problem: several observations required Inaccurate for displacements > pel multigrid methods, iteration Minimize By Bx min u 2 ( x, y, t ). y 1 x 1. T. Wiegand / B. Girod: EE398A Image and Video Compression Motion Estimation no. 12. Gradient-Based Affine Refinement Displacement vector field is represented as x a1 a2 x a3 y Combination y b1 b2 x b3 y s s . u ( x, y, t ) s( x, y, t ) s ( x, y, t t ) (a1 a2 x a3 y) (b1 b2 x b3 y). x y a1 . yields a system of linear equations: a . 2 . s s s s s s a3 . u s s , x, y, , x, y, . x x x y y y b1 . b2 .. b3 . System can be solved using, , pseudo-inverse, by minimizing arg min By Bx u 2 ( x, y, t ).

8 A1 , a2 , a3 ,b1 ,b2 ,b3 y 1 x 1. T. Wiegand / B. Girod: EE398A Image and Video Compression Motion Estimation no. 13. Block-matching Algorithm search range in Subdivide current frame previous 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 reduce computation. block of current frame Sk T. Wiegand / B. Girod: EE398A Image and Video Compression Motion Estimation no. 14. Block-matching Algorithm Previous Frame Current Frame Measurement window is Block of pixels is selected compared with a shifted block as a measurement window of pixels in the other image, to determine the best match T. Wiegand / B. Girod: EE398A Image and Video Compression Motion Estimation no.

9 15. Block-matching Algorithm Previous Frame Current Frame .. process repeated for another block. T. Wiegand / B. Girod: EE398A Image and Video Compression Motion Estimation no. 16. Error Measures for Block-matching Mean squared error (sum of squared errors). By Bx SSD(d x , d y ) [ s( x, y, t ) s ( x d x , y d y , t t )]2. y 1 x 1. Sum of absolute differences By Bx SAD (d x , d y ) | s( x, y, t ) s ( x d x , y d y , t t ) |. y 1 x 1. Approximately same performance SAD less complex for some architectures T. Wiegand / B. Girod: EE398A Image and Video Compression Motion Estimation no. 17. Block-matching: Search Strategies Full search All possible displacements within the search range are compared. dx dy Computationally expensive Highly regular, parallelizable T.

10 Wiegand / B. Girod: EE398A Image and Video Compression Motion Estimation no. 18. Speedup of Block-matching Complexity of block-matching: evaluation of complex error measure for many candidates Reduce complexity Reduce number Approximations Cover likely search areas Early terminations Unequal steps between Exclude candidates searched candidates Combine both approaches: Choose starting point and search order that maximizes likelihood for efficient approximations, early terminations and excluding of candidates T. Wiegand / B. Girod: EE398A Image and Video Compression Motion Estimation no. 19. Approximations Stop search, if match is good enough . (SSD, SAD < threshold or J=D+ R is small enough). Practical method in Video conferencing for static background: test zero-vector first and stop search if match is good enough static background T.