Video Coding BasicsYao WangPolytechnic University, Brooklyn, [email protected]© Yao Wang, 2003 EE4414: Video Coding BasicsOutline• Motivation for video coding• Basic ideas in video coding• Block diagram of a typical video codec• Different modes of operation: I, B, P• Block DCT Coding– DCT– Quantization– Run-length coding– Difference between I and P/B blocks© Yao Wang, 2003 EE4414: Video Coding Basics 3Why Compress?Video Format Y Size Color Sampling Frame Rate (Hz) Raw Data Rate (Mbps) HDTV Over air. cable, satellite, MPEG2 video, 20-45 Mbps SMPTE296M 1280x720 4:2:0 24P/30P/60P 265/332/664 SMPTE295M 1920x1080 4:2:0 24P/30P/60I 597/746/746 Video production, MPEG2, 15-50 Mbps BT.601 720x480/576 4:4:4 60I/50I 249 BT.601 720x480/576 4:2:2 60I/50I 166 High quality video distribution (DVD, SDTV), MPEG2, 4-10 Mbps BT.601 720x480/576 4:2:0 60I/50I 124 Intermediate quality video distribution (VCD, WWW), MPEG1, 1.5 Mbps SIF 352x240/288 4:2:0 30P/25P 30 Video conferencing over ISDN/Internet, H.261/H.263/MPEG4, 128-384 Kbps CIF 352x288 4:2:0 30P 37 Video telephony over wired/wireless modem, H.263/MPEG4, 20-64 Kbps QCIF 176x144 4:2:0 30P 9.1© Yao Wang, 2003 EE4414: Video Coding Basics 4Multimedia Communication StandardsStandards Application Video Format Raw Data Rate CompressedData RateH.320(H.261)Video conferencing over ISDN CIFQCIF37 Mbps9.1 Mbps>=384 Kbps>=64 KbpsH.323(H.263)Video conferencing over Internet 4CIF/ CIF/QCIF>=64 KbpsH.324(H.263)Video over phone lines/ wireless QCIF 9.1 Mbps >=18 KbpsMPEG-1 Video distribution on CD/ WWW CIF 30 Mbps 1.5 MbpsMPEG-2 Video distribution on DVD /digital TVCCIR601 4:2:0 128 Mbps 3-10 MbpsMPEG-4 Multimedia distributionover Inter/Intra netQCIF/CIF 28-1024 KbpsGA-HDTV HDTV broadcasting SMPTE296/295 <=700 Mbps 18--45 Mbps© Yao Wang, 2003 EE4414: Video Coding Basics 5Components in a Coding System© Yao Wang, 2003 EE4414: Video Coding Basics 6Image Coding Revisited• Why can we compress an image– Adjacent pixels are correlated (have similar color values)• How to compress (the JPEG way)– Use transform to decorrelate the signal (DCT)– Quantize the DCT coefficients– Runlength code the quantized indices• Zigzag ordering• Huffman coding each pair (zero runlength, non-zero value)• What is different with video?– We can apply JPEG to each video frame (Motion-JPEG)– But we can do more than that to achieve higher compression!© Yao Wang, 2003 EE4414: Video Coding Basics 7Characteristics of Typical VideosFrame t-1 Frame tAdjacent frames are similar and changes are due to object or camera motion--- Temporal correlationBackgroundMoving objects© Yao Wang, 2003 EE4414: Video Coding Basics 8Example: Two adjacent frames are similarShow difference between two frames w and w/o motion compensationFrame 66Abs olute Difference w/o Motion Compens ationFrame 69Absolute Difference with Motion Compensation© Yao Wang, 2003 EE4414: Video Coding Basics 9Key Ideas in Video Coding• Predict a new frame from a previous frame and only specify the prediction error (INTER mode)• Prediction error will be coded using an image coding method (e.g., DCT-based as in JPEG)• Prediction errors have smaller energy than the original pixel values and can be coded with fewer bits• Those regions that cannot be predicted well will be coded directly using DCT-based method (INTRA mode)• Use motion-compensated temporal prediction to account for object motion• Work on each macroblock (MB) (16x16 pixels) independently for reduced complexity– Motion compensation done at the MB level– DCT coding of error at the block level (8x8 pixels)– Block-based hybrid video coding© Yao Wang, 2003 EE4414: Video Coding Basics 10MB Structure in 4:2:0 Color Format4 8x8 Y blocks 1 8x8 Cb blocks 1 8x8 Cr blocks© Yao Wang, 2003 EE4414: Video Coding Basics 11Encoder Block Diagram of a Typical Block-Based Hybrid CoderFrom [Wang02]© Yao Wang, 2003 EE4414: Video Coding Basics 12Decoder Block DiagramFrom [Wang02]© Yao Wang, 2003 EE4414: Video Coding Basics 13Block Matching Algorithm for Motion EstimationSearch RegionFrame t-1(Reference Frame)Frame t(Predicted frame)MV© Yao Wang, 2003 EE4414: Video Coding Basics 14Block Matching Algorithm Overview• For each MB in a new (predicted) frame– Search for a block in a reference frame that has the lowest matching error • Using sum of absolute errors between corresponding pels• Search range: depends on the anticipated motion range – Displacement between the current MB and the best matching MB is the MV– Current MB is replaced by the best matching MB (motion-compensated prediction or motion compensation)• This subject will be discussed in more detail in a separate lecturemin)()()(12mDFD→−+=∑∈mBpmExxdxdψψ© Yao Wang, 2003 EE4414: Video Coding Basics 15Temporal Prediction• No Motion Compensation:– Work well in stationary regions• Uni-directional Motion Compensation:– Does not work well for uncovered regions due to object motion or newly appeared objects• Bi-directional Motion Compensation– Can handle better covered/uncovered regions$(, ,) ( , ,)ftmn ft mn=−1$(, , ) ( , , )ftmn ft m d n dxy=−−−1$(, , ) ( , , )(, , ),,,,ftmn wft m d n dwft m d n dbbxbyffxfy=−−−++−−11© Yao Wang, 2003 EE4414: Video Coding Basics 16Different Coding ModesIntra: coded directly; Predictive: predicted from a previous frame; Bidirectional: predicted from a previous frame and a following frame.Can be done at the block or frame level.From [Wang02]© Yao Wang, 2003 EE4414: Video Coding Basics 17DCT-Based Coding Revisited• Why do we use DCT: – To exploit the correlation between adjacent pixels– Typically only low frequency DCT coefficients are significant• For I-blocks, DCT is applied to original image values• For P/B-blocks, DCT is applied to prediction errorsForwardTransformQuantizerRun-Length CoderInverseTransformInverseQuantizerRun-Length DecoderInputBlockCoefficientIndicesTransformCoefficientsOutputBlockCodedBitstreamQuantizedCoefficientsChannel© Yao Wang, 2003 EE4414: Video Coding Basics 18Basis Images of 8x8 DCTLow-LowLow-HighHigh-LowHigh-High© Yao Wang, 2003 EE4414: Video Coding Basics 19DCT on a Real Image Block>>imblock = lena256(128:135,128:135)-128imblock=54 68 71 73 75 73 71 4547 52 48 14 20 24 20 -820 -10 -5 -13 -14 -21 -20 -21-13 -18 -18 -16 -23 -19 -27 -28-24 -22 -22 -26