631pub04 sec12videoMPEG

60 %
40 %
Information about 631pub04 sec12videoMPEG
Education

Published on February 27, 2008

Author: Edolf

Source: authorstream.com

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) minwu@eng.umd.edu 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)

Add a comment

Related presentations

Related pages

631pub04_sec12videoMPEG - Ace Recommendation Platform - 1

ENEE631 Digital Image Processing (Spring'04)Basic Video Coding and MPEGSpring ’04 Instructor: Min Wu ECE Department, Univ. of Maryland, College ...
Read more

631pub04_sec12videoMPEG - Ace Recommendation Platform - 38

ENEE631 Digital Image Processing (Spring'04)Lec18 – Video Coding (1) [38]
Read more

631F01_lec13 - Ace Recommendation Platform - 5

631pub04_sec12videoMPEG; CSVT2008; 631S09_lec16MPEG; DVCC_PPT2K2_CD; blockeffect; video_comp; csvt98; csvt98; mpegDecoderACMTMCCA2005; radhikaproject proposal;
Read more

631S09_lec17MPEGmore - Ace Recommendation Platform - 1

631pub04_sec12videoMPEG EE631 Digital Image Processing (Spring'04) Basic Video Coding and MPEG Spring 04 Instructor: Min Wu ECE Department, ...
Read more

631F01_lec13 - Ace Recommendation Platform - 1

Related Contents; 631pub04_sec12videoMPEG EE631 Digital Image Processing (Spring'04) Basic Video Coding and MPEG Spring 04 Instructor: Min Wu ECE ...
Read more

oh05 - Ace Recommendation Platform - 1

C.-M. Ou et al.: An Efficient VLSI Architecture for H.264 Variable Block Size Motion Estimation Contributed Paper Manuscript received September 28, 2005 ...
Read more

www-ee.uta.edu

Hier sollte eine Beschreibung angezeigt werden, diese Seite lässt dies jedoch nicht zu.
Read more

International Journal of Computer Network and Information ...

International Journal of Computer Network and Information Security(IJCNIS) ISSN: 2074-9090 (Print), ISSN: 2074-9104 (Online) Publisher: MECS
Read more

USC_TMS_CSVT07 - Ace Recommendation Platform - 4

1522 IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY, VOL. 17, NO. 11, NOVEMBER 2007matches in cross-view prediction. It combines ARF and IC ...
Read more