MPEG Video CodingOverview and LogisticsRecall: Block-Matching by Exhaustive SearchExhaustive Search: Cons and ProsFractional Accuracy Search for Block MatchingFractional Accuracy for Motion: ExampleFast Algorithms for Block MatchingFast Algorithm: 3-Step SearchHierarchical Block MatchingMotion CompensationReview: Predictive Coding with QuantizationPredictive Coding (cont’d)DCT + Motion Estimation Based Hybrid Video CodingHybrid MC-DCT Video Encoder & DecoderHybrid Video Coding: Problems to Be SolvedMPEG Video CodingAbout MPEGMPEG GenerationsMPEG-1 Video Coding StandardMPEG-1 Picture Types and Group-of-Pictures“Adaptive” Predictive Coding in MPEG-1Coding of B-frame (cont’d)Quantization for I-frame (I-block) & M.C. ResiduesAdjusting QuantizerColor TransformationVideo Coding Summary: Performance TradeoffAbout Compression RatioSummary of Today’s LectureSlide 34H.26x for Video TelephonyOther Standards and Considerations for Digital Video CodingMPEG-2Slide 40Scalability in Video CodecsSNR ScalabilitySpatial ScalabilityMPEG-4Object-based Coding in MPEG-4Slide 51MPEG-7Slide 53Slide 55Generations of Video CodingM. Wu: ENEE631 Digital Image Processing (Spring'09)MPEG Video CodingMPEG Video CodingSpring ’09 Instructor: Min Wu Electrical and Computer Engineering Department, University of Maryland, College Park bb.eng.umd.edu (select ENEE631 S’09) [email protected] Spring’09ENEE631 Spring’09Lecture 16 (4/1/2009)Lecture 16 (4/1/2009)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec16 – MPEG Video Coding [2]Overview and LogisticsOverview and LogisticsLast Time:–Block-based motion estimation–Exploit temporal redundancy via motion compensationToday:–Hybrid coding–MPEG video coding standardFriday IEEE Distinguished Lecture on image modeling–By Prof. Charles Bouman of Purdue University @ 2pm, Kim #1110"Model Based Imaging: In Search of the Free Lunch"Project#1 – Deadline extend to Friday April 10 noonAssign#4 on video and motion estimation – to post next weekUMCP ENEE631 Slides (created by M.Wu © 2004)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec16 – MPEG Video Coding [3]Recall: Block-Matching by Exhaustive SearchRecall: Block-Matching by Exhaustive SearchModeling: assume movements are block-based translation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.6UMCP ENEE408G Slides (created by M.Wu & R.Liu © 2002)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec16 – MPEG Video Coding [5]Exhaustive Search: Cons and ProsExhaustive 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Per block complexity is proportional to block size and search rangeOn the order of [search-range-size x image-size] for 1-pixel step size How to improve accuracy?–Include blocks at fractional translation as candidates => consider a higher resolution frame using interpolation How to improve speed and computational complexity?–Try to exclude unlikely candidatesUMCP ENEE408G Slides (created by M.Wu & R.Liu © 2002)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec16 – MPEG Video Coding [6]Fractional Accuracy Search for Block MatchingFractional 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)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec16 – MPEG Video Coding [7]No motion compensation1-pixel precision½ pixel precision¼ pixel precisionFractional Accuracy for Motion: ExampleFractional Accuracy for Motion: ExampleFrom Gonzalez-Woods 3/e Fig. 8.38M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec16 – MPEG Video Coding [8]Fast Algorithms for Block MatchingFast 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 matchUMCP ENEE408G Slides (created by M.Wu & R.Liu © 2002)(From Wang’s Preprint Fig.6.6)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec16 – MPEG Video Coding [9]M24M15M14M13M16M11M12M5M4M3M17M18M19-6M6M1M2+6M7M8M9dxdyFast 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 rangemotion vector {dx, dy} = {1, 6}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)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec16 – MPEG Video Coding [10]Lowest resolutionmedium resolutionOriginal resolutionHierarchical Block MatchingHierarchical 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)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec16 – MPEG Video Coding [11]Motion Compensation Motion Compensation A form of predictive coding to reduce temporal redundancy of video PREVIOUS FRAME CURRENT FRAMEPREDICTED FRAME PREDICTION ERROR FRAMEUMCP ENEE408G Slides (created by M.Wu & R.Liu © 2002)Revised from R.Liu Seminar Course ’00 @ UMDM. Wu: ENEE631 Digital Image Processing (Spring'09) Lec16 – MPEG Video Coding [12]Review: Predictive Coding with QuantizationReview: Predictive Coding with QuantizationConsider: high correlation between successive samplesPredictive coding–Basic principle: Remove redundancy between successive pixels and only encode residual between