631pub04 sec12videoMPEG

Information about 631pub04 sec12videoMPEG

Published on February 27, 2008

Author: Edolf

Source: authorstream.com

Content

Basic Video Coding and MPEG:  Basic Video Coding and MPEG Spring ’04 Instructor: Min Wu ECE Department, Univ. of Maryland, College Park www.ajconline.umd.edu (select ENEE631 S’04) [email protected] UMCP ENEE631 Slides (created by M.Wu © 2004) Based on ENEE631 Spring’04 Section 12 Overview and Logistics:  Overview and Logistics Last Time: Bit allocation issues in image coding Optimal unitary transform – KLT Question-for-Today: How to efficiently code motion pictures Today: Finish optimal unitary transform => See slides handout from Lecture 17 Hybrid video coding Block-based motion estimation and compensation UMCP ENEE631 Slides (created by M.Wu © 2004) Motion Pictures:  Motion Pictures UMCP ENEE631 Slides (created by M.Wu © 2004) Bring in Motion  Video (Motion Pictures):  Bring in Motion  Video (Motion Pictures) Capturing video Frame by frame => image sequence Image sequence: A 3-D signal 2 spatial dimensions & time dimension continuous I( x, y, t ) => discrete I( m, n, tk ) Encode digital video Simplest way ~ compress each frame image individually e.g., “motion-JPEG” only spatial redundancy is explored and reduced How about temporal redundancy? Is differential coding good? Pixel-by-pixel difference could still be large due to motion  Need better prediction UMCP ENEE408G Slides (created by M.Wu & R.Liu © 2002) Slide5:  (From Princeton EE330 S’01 by B.Liu) Pixel-wise difference w/o motion compensation “Horse ride” UMCP ENEE408G Slides (created by M.Wu & R. Liu © 2002) Motion Estimation:  Motion Estimation Help understanding the content of image sequence For surveillance Help reduce temporal redundancy of video For compression Stabilizing video by detecting and removing small, noisy global motions For building stabilizer in camcorder UMCP ENEE408G Slides (created by M.Wu & R.Liu © 2002) Block-Matching by Exhaustive Search:  Block-Matching by Exhaustive Search Assume block-based translation motion model Search every possibility over a specified range for the best matching block MAD (mean absolute difference) often used for simplicity Flash Demo (by Dr. Ken Lam @ Hong Kong PolyTech Univ.) From Wang’s Preprint Fig.6.6 UMCP ENEE408G Slides (created by M.Wu & R.Liu © 2002) Motion Compensation :  Motion Compensation Help reduce temporal redundancy of video PREVIOUS FRAME CURRENT FRAME PREDICTED FRAME PREDICTION ERROR FRAME UMCP ENEE408G Slides (created by M.Wu & R.Liu © 2002) Revised from R.Liu Seminar Course ’00 @ UMD Complexity of Exhaustive Block-Matching:  Complexity of Exhaustive Block-Matching Assumptions Block size NxN and image size S=M1xM2 Search step size is 1 pixel ~ “integer-pel accuracy” Search range +/–R pixels both horizontally and vertically Computation complexity # Candidate matching blocks = (2R+1)2 # Operations for computing MAD for one block ~ O(N2) # Operations for MV estimation per block ~ O((2R+1)2 N2) # Blocks = S / N2 Total # operations for entire frame ~ O((2R+1)2 S) i.e., overall computation load is independent of block size! E.g., M=512, N=16, R=16, 30fps => On the order of 8.55 x 109 operations per second! Was difficult for real time estimation, but possible with parallel hardware UMCP ENEE408G Slides (created by M.Wu & R.Liu © 2002) Exhaustive Search: Cons and Pros:  Exhaustive Search: Cons and Pros Pros Guaranteed optimality within search range and motion model Cons Can only search among finitely many candidates What if the motion is “fractional”? High computation complexity On the order of [search-range-size * image-size] for 1-pixel step size  How to improve accuracy? Include blocks at fractional translation as candidates => require interpolation  How to improve speed? Try to exclude unlikely candidates UMCP ENEE408G Slides (created by M.Wu & R.Liu © 2002) Fractional Accuracy Search for Block Matching:  Fractional Accuracy Search for Block Matching For motion accuracy of 1/K pixel Upsample (interpolate) reference frame by a factor of K Search for the best matching block in the upsampled reference frame Half-pel accuracy ~ K=2 Significant accuracy improvement over integer-pel (esp. for low-resolution) Complexity increase (From Wang’s Preprint Fig.6.7) UMCP ENEE408G Slides (created by M.Wu & R.Liu © 2002) Fast Algorithms for Block Matching:  Fast Algorithms for Block Matching Basic ideas Matching errors near the best match are generally smaller than far away Skip candidates that are unlikely to give good match UMCP ENEE408G Slides (created by M.Wu & R.Liu © 2002) (From Wang’s Preprint Fig.6.6) Fast Algorithm: 3-Step Search :  Fast Algorithm: 3-Step Search Search candidates at 8 neighbor positions Step-size cut down by 2 after each iteration Start with step size approx. half of max. search range Total number of computations: 9 + 82 = 25 (3-step) (2R+1)2 = 169 (full search) (Fig. from Ken Lam – HK Poly Univ. short course in summer’2001) UMCP ENEE408G Slides (created by M.Wu & R.Liu © 2002) => See Flash demo by Jane Kim (UMD) Hierarchical Block Matching:  Hierarchical Block Matching Problem with fast search at full resolution Small mis-alignment may give high displacement error (EDFD) esp. for texture and edge blocks Hierarchical (multi-resolution) block matching Match with coarse resolution to narrow down search range Match with high resolution to refine motion estimation (From Wang’s Preprint Fig.6.19) UMCP ENEE408G Slides (created by M.Wu & R.Liu © 2002) Hybrid Coding for Video :  Hybrid Coding for Video UMCP ENEE631 Slides (created by M.Wu © 2004) DCT-M.E. Hybrid Video Coding:  DCT-M.E. Hybrid Video Coding “Hybrid” ~ combined transform coding & predictive coding Spatial redundancy removal Use DCT-based transform coding for reference frame Temporal redundancy removal Use motion-based predictive coding for next frames estimate motion and use reference frame to predict only encode MV & prediction residue (“motion compensation residue”) (From Princeton EE330 S’01 by B.Liu) UMCP ENEE408G Slides (created by M.Wu & R.Liu © 2002) Review: Predictive Coding with Quantization:  Review: Predictive Coding with Quantization Consider: high correlation between successive samples Predictive coding Basic principle: Remove redundancy between successive pixels and only encode residual between actual and predicted Residue usually has much smaller dynamic range Allow fewer quantization levels for the same MSE => get compression Compression efficiency depends on intersample redundancy First try: Any problem with this codec? UMCP ENEE408G Slides (created by M.Wu & R.Liu © 2002) Predictive Coding (cont’d):  Predictive Coding (cont’d) Problem with 1st try Input to predictor are different at encoder and decoder decoder doesn’t know u(n)! Mismatch error could propagate to future reconstructed samples Solution: Differential PCM (DPCM) Use quantized sequence uQ(n) for prediction at both encoder and decoder Simple predictor f[ x ] = x Prediction error e(n) Quantized prediction error eQ(n) Distortion d(n) = e(n) – eQ(n) UMCP ENEE408G Slides (created by M.Wu & R.Liu © 2002) Note: “Predictor” contains one-step buffer as input to the prediction Hybrid MC-DCT Video Encoder:  Hybrid MC-DCT Video Encoder (From R.Liu’s Handbook Fig.2.18) Intra-frame: encoded without prediction Inter-frame: predictively encoded => use quantized frames as ref for residue UMCP ENEE408G Slides (created by M.Wu & R.Liu © 2002) Hybrid MC-DCT Video Decoder:  Hybrid MC-DCT Video Decoder (From R.Liu’s Handbook Fig.2.18) UMCP ENEE408G Slides (created by M.Wu & R.Liu © 2002) Recall: Motion Compensation :  Recall: Motion Compensation Help reduce temporal redundancy of video PREVIOUS FRAME CURRENT FRAME PREDICTED FRAME PREDICTION ERROR FRAME UMCP ENEE408G Slides (created by M.Wu & R.Liu © 2002) Revised from R.Liu Seminar Course ’00 @ UMD Hybrid Video Coding: Problems to Be Solved:  Hybrid Video Coding: Problems to Be Solved Not all regions are easily inferable from previous frame Occlusion ~ solvable by backward prediction using future frames as ref. Adaptively decide using prediction or not Drifting and error propagation Solution: Encode reference regions or frames from time to time Random access Solution: Encode frame without prediction from time to time How to allocate bits? Based on visual model and statistics: JPEG-like quant. steps; entropy coding Consider constant or variable bit-rate requirement Constant-bit-rate (CER) vs. Variable-bit-rate (VER)  Wrap up all solutions ~ MPEG-like codec UMCP ENEE408G Slides (created by M.Wu & R.Liu © 2002) MPEG Video Coding :  MPEG Video Coding UMCP ENEE631 Slides (created by M.Wu © 2004) About MPEG:  About MPEG MPEG – Moving Pictures Experts Group Coding of moving pictures and associated audio Basic compression idea on the picture part Can achieve compression ratio of about 50:1 through storing only the differences between successive frames Some claim higher compression ratio Depends on how we calculate Notice color is often downsampled, and interleaving odd/even fields Audio part Compression of audio data at ratios ranging from 5:1 to 10:1 MP3 ~ “MPEG-1 audio Layer-3” UMCP ENEE408G Slides (created by M.Wu & R.Liu © 2002) Progressive vs. Interlaced scan:  Progressive vs. Interlaced scan From B.Liu EE330 S’01 Princeton UMCP ENEE631 Slides (created by M.Wu © 2001) Compression Ratio:  Compression Ratio Raw video 24 bits/pixel x (720 x 480 pixels) x 30 fps = 249 Mbps Potential “cheating” points => contributing ~4:1 inflation Color components are actually downsampled 30 fps may refer to field rate in MPEG-2 ~ equiv. to 15 fps ( 8 x 720 x 480 + 16 x 720 x 480 / 4 ) x 15 fps = 62 Mbps UMCP ENEE408G Slides (created by M.Wu & R.Liu © 2002) MPEG Generations:  MPEG Generations MPEG-1 ~ 1-1.5Mbps (early 90s) For compression of 320x240 full-motion video at rates around 1.15Mb/s Applications: video storage (VCD) MPEG-2 ~ 2-80Mbps (mid 90s) For higher resolutions Support interlaced video formats and a number of features for HDTV Address scalable video coding Also used in DVD MPEG-4 ~ 9-40kbps (later 90s) For very low bit rate video and audio coding Applications: interactive multimedia and video telephony MPEG-21 ~ ongoing UMCP ENEE408G Slides (created by M.Wu & R.Liu © 2002) MPEG Generations (cont’d):  MPEG Generations (cont’d) (From Ken Lam – HK Poly Univ. short course in summer’2001) UMCP ENEE408G Slides (created by M.Wu & R.Liu © 2002) MPEG-1 Video Coding Standard:  MPEG-1 Video Coding Standard Standard only specifies decoders’ capabilities Prefer simple decoding and not limit encoder’s complexity Leave flexibility and competition in implementing encoder Block-based hybrid coding (DCT + M.C.) 8x8 block size as basic coding unit 16x16 “macroblock” size for motion estimation/compensation Group-of-Picture (GOP) structure with 3 types of frames Intra coded Forward-predictively coded Bidirectional-predictively coded UMCP ENEE408G Slides (created by M.Wu & R.Liu © 2002) MPEG-1 Picture Types and Group-of-Pictures:  MPEG-1 Picture Types and Group-of-Pictures A Group-of-Picture (GOP) contains 3 types of frames (I/P/B) Frame order I1 BBB P1 BBB P2 BBB I2 … Coding order I1 P1 BBB P2 BBB I2 BBB … (From R.Liu Handbook Fig.3.13) UMCP ENEE408G Slides (created by M.Wu & R.Liu © 2002) “Adaptive” Predictive Coding in MPEG-1:  “Adaptive” Predictive Coding in MPEG-1 Half-pel M.V. search within +/-64 pel range Use spatial differential coding on M.V. to remove M.V. spatial redundancy Coding each block in P-frame Predictive block using previous I/P frame as reference Intra-block ~ encode without prediction use this if prediction costs more bits than non-prediction good for occluded area can also avoid error propagation Coding each block in B-frame Intra-block ~ encode without prediction Predictive block Use previous I/P frame as reference (forward prediction), Or use future I/P frame as reference (backward prediction), Or use both for prediction and take average UMCP ENEE408G Slides (created by M.Wu & R.Liu © 2002) Coding of B-frame (cont’d):  Coding of B-frame (cont’d) UMCP ENEE408G Slides (created by M.Wu & R.Liu © 2002) (Fig. from Ken Lam – HK Poly Univ. short course in summer’2001) Quantization for I-frame (I-block) & M.C. Residues :  Quantization for I-frame (I-block) & M.C. Residues Quantizer for I-frame (I-block) Different step size for different freq. band (similar to JPEG) Default quantization table Scale the table for different compression-quality Quantizer for residues in predictive block Noise-like residue Similar variance in different freq. band Assign same quantization step size for each freq. band UMCP ENEE408G Slides (created by M.Wu & R.Liu © 2002) Revised from R.Liu Seminar Course ’00 @ UMD Adjusting Quantizer:  Adjusting Quantizer For smoothing out bit rate Some applications prefer approx. constant bit rate video stream (CBR) e.g., prescribe # bits per second very-short-term bit-rate variations can be smoothed by a buffer variations can’t be too large on longer term ~ o.w. buffer overflow Need to assign large step size for complex and high-motion frames For reducing bit rate by exploiting HVS temporal properties Noise/distortion in a video frame would not be very much visible when there is a sharp temporal transition (scene change) can compress a few frames right after scene change with less bits Alternative bit-rate adjustment tool ~ frame type I I I I I I … lowest compression ratio (like motion-JPEG) I P P … P I P P … moderate compression ratio I B B P B B P B B I … highest compression ratio UMCP ENEE631 Slides (created by M.Wu © 2001) Color Transformation:  Color Transformation RGB  YUV color coordinates U/V chrominance components are downsampled in coding UMCP ENEE408G Slides (created by M.Wu & R.Liu © 2002) Color Formats:  Color Formats UMCP ENEE408G Slides (created by M.Wu & R.Liu © 2002) Revised from R.Liu Seminar Course ’00 @ UMD Video Coding Summary: Performance Tradeoff:  Video Coding Summary: Performance Tradeoff From R.Liu’s Handbook Fig.1.2: “mos” ~ 5-pt mean opinion scale of bad, poor, fair, good, excellent UMCP ENEE408G Slides (created by M.Wu & R.Liu © 2002) Summary of Today’s Lecture:  Summary of Today’s Lecture Optimal unitary transform: Optimality of KLT; relation with DCT Video coding Dealing with spatial and temporal redundancy Block-based motion estimation and compensation Next Lecture: Hybrid video coding, MPEG Readings Wang’s book 9.1.6 (KLT vs DCT); 9.3.1 (basics on video coding); 6.4 (block matching) UMCP ENEE631 Slides (created by M.Wu © 2004) Summary:  Summary Motion estimation Video compression through hybrid coding Exploit spatial redundancy via transform coding Exploit temporal redundancy via predictive coding motion estimation and compensation MPEG-1 video compression Hybrid DCT-ME coding standard Friday lab session: video compression Next Lecture: video processing and analysis UMCP ENEE408G Slides (created by M.Wu © 2002) Assignment:  Assignment Readings: (see E-handout in course webpage) “Data Compression” from Lecture 3 Section 7.7 MPEG (for 7.7.5 MPEG-4, only need to read till 7.7.5.3) For more details on video coding => see instructor for copies Liu’s Chapter 2 “Motion-Compensated DCT Video Coding” Liu’s Chapter 3 “Video Coding Standards” UMCP ENEE408G Slides (created by M.Wu © 2002)

Related presentations


Other presentations created by Edolf

Chapter 02
30. 12. 2007
0 views

Chapter 02

Sauli GEM
29. 10. 2007
0 views

Sauli GEM

IV Classical
26. 11. 2007
0 views

IV Classical

flex builder debugger
28. 11. 2007
0 views

flex builder debugger

Powell
04. 12. 2007
0 views

Powell

CLC History Part I
29. 10. 2007
0 views

CLC History Part I

ActivityDiagrams
06. 11. 2007
0 views

ActivityDiagrams

Perriono Helsinki TFMM
01. 11. 2007
0 views

Perriono Helsinki TFMM

IT
06. 11. 2007
0 views

IT

GKII005
16. 11. 2007
0 views

GKII005

Using Doubles in Math
16. 11. 2007
0 views

Using Doubles in Math

Creative Dance
23. 11. 2007
0 views

Creative Dance

Opac Tutorial Module 3
26. 11. 2007
0 views

Opac Tutorial Module 3

LaszloAndWebOrb
28. 11. 2007
0 views

LaszloAndWebOrb

McCarthy Hearings
24. 12. 2007
0 views

McCarthy Hearings

International politics
28. 12. 2007
0 views

International politics

InnoArdentBridgesABC 04 01 23 07
01. 01. 2008
0 views

InnoArdentBridgesABC 04 01 23 07

class presentation
02. 01. 2008
0 views

class presentation

420 07 lect2
03. 01. 2008
0 views

420 07 lect2

stiles
03. 01. 2008
0 views

stiles

Civic Engagement
07. 01. 2008
0 views

Civic Engagement

How to Make Biodiesel D Geller
12. 11. 2007
0 views

How to Make Biodiesel D Geller

The Agricultural World Part I
27. 11. 2007
0 views

The Agricultural World Part I

VUS06 07
12. 12. 2007
0 views

VUS06 07

6 Choice of Law
31. 10. 2007
0 views

6 Choice of Law

page9 1
20. 02. 2008
0 views

page9 1

ACCRA PP Show June
24. 02. 2008
0 views

ACCRA PP Show June

who1105
27. 03. 2008
0 views

who1105

NCSA
06. 11. 2007
0 views

NCSA

Introduzione
21. 11. 2007
0 views

Introduzione

Lect 23
14. 12. 2007
0 views

Lect 23

EAPN 0604 turkey2
28. 11. 2007
0 views

EAPN 0604 turkey2

sigcse97
10. 12. 2007
0 views

sigcse97

8 NASS Aug Rpt
04. 10. 2007
0 views

8 NASS Aug Rpt

caca ao tesouro
31. 12. 2007
0 views

caca ao tesouro

Lec3 Ling
19. 11. 2007
0 views

Lec3 Ling

Corrie
22. 11. 2007
0 views

Corrie

Ancient Greece and Rome
30. 10. 2007
0 views

Ancient Greece and Rome