Basics on Video CodingOverview and LogisticsImage Interpolation: A Quick Extension from 1-D Interpolation Useful in image enlargement, rotation, motion estimation, etc.Examples of Image InterpolationInterpolation / ZoomingReview: 1-D Frequency-Domain InterpretationFrequency-Domain InterpretationMore on InterpolationFrom Image Coding to Video CodingReviewBring in Motion  Video (Motion Pictures)Video ExamplesExplore Temporal Redundancy – 1st tryExplore MotionMotion EstimationBlock-Matching by Exhaustive SearchMotion CompensationComplexity of Exhaustive Block-MatchingExhaustive Search: Cons and ProsFractional Accuracy Search for Block MatchingFractional Accuracy for Motion: ExampleFast Algorithms for Block MatchingFast Algorithm: 3-Step SearchHierarchical Block MatchingSummary of Today’s LectureHybrid Coding for VideoDCT-M.E. Hybrid Video CodingReview: Predictive Coding with QuantizationPredictive Coding (cont’d)Hybrid MC-DCT Video EncoderHybrid MC-DCT Video DecoderHybrid Video Coding: Problems to Be SolvedSlide 40Slide 41Background Reviews on Video Acquisition and DisplayVideo CameraVideo DisplayComposite vs. Component VideoAnalog Video RasterForming Picture on TV Tube (Monochrome)How Many TV Lines?Progressive vs. Interlaced scanAnalog Color TV SystemsComparison of Three Analog TV SystemsNTSCNTSC 6MHz BandwidthAnalog Video RecordingDigital Video FormatsSummary: Source Video FormatsChannel BandwidthsChannel Bandwidth (cont’d)Application RequirementsSlide 61M. Wu: ENEE631 Digital Image Processing (Spring'09)Basics on Video CodingBasics on 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 15 (3/30/2009)Lecture 15 (3/30/2009)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec15 – Hybrid Video Coding [2]Overview and LogisticsOverview and LogisticsLast Time:–Bit allocation issues in image compression–Optimal transform KLT ~ unitary transform; decorrelate dataoptimal MMSE approximation under basis restrictionComments on issues arising from mid-term exam–Linearity and shift invariance: check by definitionIs piecewise linear stretching a linear operation?If ignoring boundary effect, are median filtering and point operations (including histogram based processing) shift invariant?Give examples on shift variant operations–Quantization: MMSE criterion vs. Minmax criterionToday:–Image interpolation–Video coding: explore temporal and spatial redundancyUMCP ENEE631 Slides (created by M.Wu © 2004)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec15 – Hybrid Video Coding [5]Image Interpolation: Image Interpolation: A Quick Extension from 1-D InterpolationA Quick Extension from 1-D Interpolation Useful in image enlargement, rotation, motion estimation, etc.Useful in image enlargement, rotation, motion estimation, etc.UMCP ENEE631 Slides (created by M.Wu © 2004)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec15 – Hybrid Video Coding [6]Examples of Image InterpolationExamples of Image Interpolation4x zoom (nearest neighbor) 4x zoom (bilinear)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec15 – Hybrid Video Coding [7]Interpolation / ZoomingInterpolation / ZoomingHow to make up the new pixels?Replication according to the nearest neighbor–Simple but leaves zig-zag boundary (reflect spectrum artifacts; equiv. to interlace zero & LPF with a constant mask)(p,q)(p’,q’)(p,q+1)(p+1,q+1)(p+1,q)aba 1-af1f2– Do two horizontal and one vertical 1-D interpolation F( p’, q’ ) = (1-a) [ (1-b) F(p, q) + b F(p, q+1) ] + a [(1-b) F(p+1, q) + b F(p+1, q+1) ]For zoom in by 2 in each dimension:F(p’, q’) = 0.5  [0.5 F(p,q) + 0.5 F(p,q+1)] + 0.5  [0.5 F(p+1,q) + 0.5 F(p+1,q+1)]=> equiv. to F(x, y) = r x + s y + u xy + v solve parameters using 4 known pixels Bilinear interpolation– Extend 1-D linear interpolation: (1-a) f1 + a f2UMCP ENEE631/408G Slides (created by M.Wu © 2001/2002)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec15 – Hybrid Video Coding [8]Review: 1-D Frequency-Domain InterpretationReview: 1-D Frequency-Domain InterpretationFrom Crochiere-Rabiner “Multirate DSP” book Fig.2.15-16M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec15 – Hybrid Video Coding [9]Frequency-Domain InterpretationFrequency-Domain InterpretationReview multirate signal processing (ENEE630)For Images: extend to the 2-D transformDownsampling–Aliasing as spectra replicas becomes closer–LPF to avoid aliasingUpsampling–Upsampling with zero interlacing ~ replicated spectrum–LPF to filter out the spectra replicas in high-frequency part–Ideal filter vs. practical filters nearest neighbor approach for 2x zoom use [think] what equiv. filters used for bilinear interpolation?Sampling rate conversion with rational rate M / N–Upsample with zero interlacing by M  LPF  Downsample1 11 1UMCP ENEE631 Slides (created by M.Wu © 2001)1/2 11/4 1/21/4 1/21/21/41/4M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec15 – Hybrid Video Coding [11]More on InterpolationMore on InterpolationOther filters –Bi-cubic interpolation (3rd order polynomial on index variables)Based on combination of 16-pixel neighborhood–Can build p-th order interpolation by recursive filteringAfter upsample by p, convolve with linear interpolation filter p timesInterpolation that avoids blurred edges and textures–Sharpening–Edge-preserving interpolation( recent research papers in ICIP and Trans. on Image Proc. )=> Will discuss more on 2-D sampling and frequency domain interpretation in a few lecturesUMCP ENEE631 Slides (created by M.Wu © 2001/2004)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec15 – Hybrid Video Coding [13]From Image Coding to Video CodingFrom Image Coding to Video Coding UMCP ENEE631 Slides (created by M.Wu © 2004)M. Wu: ENEE631 Digital Image Processing (Spring'09) Lec15 – Hybrid Video Coding [14]ReviewReviewBasic tools for compression–PCM coding, entropy coding, run-length coding–Quantization and truncation–Predictive coding–Transform coding: DCT-basedJPEG image compression–8x8 Block-DCT based transform coding–Use predictive coding, quantization, run-length coding, and entropy codingToday: digital video and video compressionUMCP