slide10_Basic Video Compression Techniques

FundamentalsofMultimedia,Chapter10Chapter10BasicVideoCompressionTechniques10.1IntroductiontoVideoCompression10.2VideoCompressionwithMotionCompensation10.3SearchforMotionVectors10.4H.26110.5H.26310.6FurtherExploration1FundamentalsofMultimedia,Chapter1010.1IntroductiontoVideoCompression•Avideoconsistsofatime-orderedsequenceofframes,i.e.,images.•Anobvioussolutiontovideocompressionwouldbepredictivecodingbasedonpreviousframes.Compressionproceedsbysubtractingimages:subtractintimeorderandcodetheresidualerror.•Itcanbedoneevenbetterbysearchingforjusttherightpartsoftheimagetosubtractfromthepreviousframe.2FundamentalsofMultimedia,Chapter1010.2VideoCompressionwithMotionCompensation•Consecutiveframesinavideoaresimilar—temporalredun-dancyexists.•Temporalredundancyisexploitedsothatnoteveryframeofthevideoneedstobecodedindependentlyasanewimage.Thedifferencebetweenthecurrentframeandotherframe(s)inthesequencewillbecoded—smallvaluesandlowentropy,goodforcompression.•StepsofVideocompressionbasedonMotionCompensation(MC):1.MotionEstimation(motionvectorsearch).2.MC-basedPrediction.3.Derivationofthepredictionerror,i.e.,thedifference.3FundamentalsofMultimedia,Chapter10MotionCompensation•EachimageisdividedintomacroblocksofsizeN×N.–Bydefault,N=16forluminanceimages.Forchrominanceimages,N=8if4:2:0chromasubsamplingisadopted.•Motioncompensationisperformedatthemacroblocklevel.–ThecurrentimageframeisreferredtoasTargetFrame.–AmatchissoughtbetweenthemacroblockintheTargetFrameandthemostsimilarmacroblockinpreviousand/orfutureframe(s)(referredtoasReferenceframe(s)).–Thedisplacementofthereferencemacroblocktothetargetmac-roblockiscalledamotionvectorMV.–Figure10.1showsthecaseofforwardpredictioninwhichtheRefer-enceframeistakentobeapreviousframe.4(x,y)(x0,y0)NNFundamentalsofMultimedia,Chapter10TargetframeMatchedmacroblockReferenceframeSearchwindow(x,y)2p+12p+1MV(x0,y0)Fig.10.1:MacroblocksandMotionVectorinVideoCompression.•MVsearchisusuallylimitedtoasmallimmediateneighborhood—bothhorizontalandverticaldisplacementsintherange[−p,p].Thismakesasearchwindowofsize(2p+1)×(2p+1).5FundamentalsofMultimedia,Chapter1010.3SearchforMotionVectors•Thedifferencebetweentwomacroblockscanthenbemea-suredbytheirMeanAbsoluteDifference(MAD):MAD(i,j)=1N2N−1N−1k=0l=0|C(x+k,y+l)−R(x+i+k,y+j+l)|(10.1)N–sizeofthemacroblock,kandl–indicesforpixelsinthemacroblock,iandj–horizontalandverticaldisplacements,C(x+k,y+l)–pixelsinmacroblockinTargetframe,R(x+i+k,y+j+l)–pixelsinmacroblockinReferenceframe.•Thegoalofthesearchistofindavector(i,j)asthemotionvectorMV=(u,v),suchthatMAD(i,j)isminimum:(u,v)=[(i,j)|MAD(i,j)isminimum,i∈[−p,p],j∈[−p,p]](10.2)6FundamentalsofMultimedia,Chapter10SequentialSearch•Sequentialsearch:sequentiallysearchthewhole(2p+1)×(2p+1)windowintheReferenceframe(alsoreferredtoasFullsearch).–amacroblockcenteredateachofthepositionswithinthewindowiscomparedtothemacroblockintheTargetframepixelbypixelandtheirrespectiveMADisthenderivedusingEq.(10.1).–Thevector(i,j)thatofferstheleastMADisdesignatedastheMV(u,v)forthemacroblockintheTargetframe.–sequentialsearchmethodisverycostly—assumingeachpixelcomparisonrequiresthreeoperations(subtraction,absolutevalue,addition),thecostforobtainingamotionvectorforasinglemacroblockis(2p+1)·(2p+1)·N2·3⇒O(p2N2).7FundamentalsofMultimedia,Chapter10PROCEDURE10.1Motion-vector:sequential-searchbegin/*Initialization*/minMAD=LARGENUMBER;fori=−ptopforj=−ptop{curMAD=MAD(i,j);ifcurMADminMAD{minMAD=curMAD;/*GetthecoordinatesforMV.*/u=i;v=j;}}end8FundamentalsofMultimedia,Chapter102DLogarithmicSearch•Logarithmicsearch:acheaperversion,thatissuboptimalbutstillusuallyeffective.•Theprocedurefor2DLogarithmicSearchofmotionvectorstakesseveraliterationsandisakintoabinarysearch:–AsillustratedinFig.10.2,initiallyonlyninelocationsinthesearchwindowareusedasseedsforaMAD-basedsearch;theyaremarkedas‘1’.–AftertheonethatyieldstheminimumMADislocated,thecenterofthenewsearchregionismovedtoitandthestep-size(”offset”)isreducedtohalf.–Inthenextiteration,theninenewlocationsaremarkedas‘2’,andsoon.92232333312121222111(x0,y0)111p/2FundamentalsofMultimedia,Chapter10333(x0−p,y0−p)(x0−p,y0+p)(x0+p,y0+p)(x0+p,y0−p)Fig.10.2:2DLogarithmicSearchforMotionVectors.10FundamentalsofMultimedia,Chapter10PROCEDURE10.2Motion-vector:2D-logarithmic-searchbeginoffset=p2;SpecifyninemacroblockswithinthesearchwindowintheReferenceframe,theyarecenteredat(x0,y0)andseparatedbyoffsethorizontallyand/orvertically;whilelast=TRUE{FindoneoftheninespecifiedmacroblocksthatyieldsminimumMAD;ifoffset=1thenlast=TRUE;offset=offset/2;Formasearchregionwiththenewoffsetandnewcenterfound;}end11FundamentalsofMultimedia,Chapter10•Usingthesameexampleasintheprevioussubsection,thetotaloperationspersecondisdroppedto:720×480N·N720×48016×16≈1.25×10912FundamentalsofMultimedia,Chapter10HierarchicalSearch•Thesearchcanbenefitfromahierarchical(multiresolution)approachinwhichinitialestimationofthemotionvectorcanbeobtainedfromimageswithasignificantlyreducedresolution.•Figure10.3:athree-levelhierarchicalsearchinwhichtheoriginalimageisatLevel0,imagesatLevels1and2areob