!!!! A Search Patterns Switching Algorithm for Block Motion

!!!! A Search Patterns Switching Algorithm for Block Motion Estimation

ASearchPatternsSwitchingAlgorithmforBlockMotionEstimation

Ka-HoNg,Lai-ManPo,Ka-ManWong,Chi-WangTing,andKwok-WaiCheung

Abstract—Center-biasedfastmotionestimationalgorithms,e.g.,block-basedgradientdescentsearchanddiamondsearch,canperformmuchbetterthancoarse-to- nesearch

algorithms,suchas2-Dlogarithmicsearchandthree-stepsearch.Thelattertypeofalgorithms,however,ismoresuitableforhandlinglargemotioncontent.Tocombinetheadvantagesofbothtypesofalgorithms,anadaptivealgorithmperformingsearchpatternsswitching(SPS)isproposedinthispaper.TheproposedSPSalgorithmclassi esthemotioncontentofablockusingasimpleyetef cientmotioncontentclassi ercallederrordescentrate.Unlikeotherclassi erswithheavyoverhead,thisclassi errequiresonlythesearchingofafewpointsinthesearchwindowandthenadivisionoperation.ExperimentalresultsshowthattheproposedSPSalgorithmisveryrobust.

IndexTerms—Blockmatching,motionestimation,videocoding.

I.INTRODUCTION

Blockmatchingalgorithms(BMAs)havebeenwidelyusedinmotionestimation(ME)forvariousvideocodingstan-dardssuchastheH.26Xseries[1].Fullsearch(FS)canobtaintheoptimalmotionvectors(MVs)butitisveryslow.ManyfastBMAs(FBMAs)havebeenproposedtospeeduptheMEprocessbyreducingthenumberofsearchpointsbasedontwoapproaches.Oneapproach,asemployedin2-Dlogarithmicsearch(2-DLOG)[2]andthree-stepsearch(3SS)[3],usescoarse-to- nesearchingtoreducethenumberofsearchpoints.Thisapproachisef cientforlarge-motionvideosequencesbecauseinthesesequencesthesearchpointsareevenlydistributedoverthesearchwindowandthustheglobalminimafarawayfromwindowcenterscanbelocatedmoreef ciently.Forsmallmotions,thisapproachislessef cient.

Thesecondapproachutilizesthecenter-biasedcharacteristicofMVs.Accordingtoananalysisonmotionvectordistri-butionin[4],abouthalfofthemacro-blocksarestationaryandmostoftheMVsliewithinthecentral5×5regionofthesearchwindow.Algorithmssuchasnewthree-stepsearch(N3SS)[5],four-stepsearch(4SS)[6],block-basedgradientdescentsearch(BBGDS)[7],diamondsearch(DS)[8],andcrossdiamondsearch(CDS)[4]usecenter-biased

ManuscriptreceivedJanuary26,2008;revisedJune6,2008.FirstversionpublishedMarch16,2009;currentversionpublishedJune10,2009.ThisworkwassupportedbyagrantfromCityUniversityofHongKong,HongKongSAR,ChinaunderProject9041251(CityU119207).ThispaperwasrecommendedbyAssociateEditorL.Chen.

K.-H.Ng,L.-M.Po,K.-M.Wong,andC.-W.TingarewiththeDe-partmentofElectronicEngineering,CityUniversityofHongKong,HongKongSAR,China(e-mail:kahomike@http://;eelmpo@cityu.edu.hk;kmwong@ee.cityu.edu.hk;cwting@cityu.edu.hk).

K.-W.CheungiswiththeDepartmentofComputerScience,ChuHaiCollegeofHigherEducation,HongKongSAR,China(e-mail:kwche-ung@chuhai.edu.hk).

DigitalObjectIdenti er10.1109/TCSVT.2009.2017414

http://paredwithcoarse-to- nesearchalgorithms,asubstantialreductionofsearchpointscanbeachievedforsmallmotionsequences.Forvideoswithlargemotions,however,theyaresubjecttoqualitydegradationbecausetheycanbeeasilytrappedinlocalminima.

Adaptivealgorithmscombinetheadvantagesoftheabovetwoapproachesbyusingdifferentsearchpatternsaccordingtothemotioncontentofablock.Theperformanceofanadaptivealgorithmdependsontheaccuracyofitsmotioncontentclassi cation.

Inthispaper,anadaptivesearchpatternsswitching(SPS)algorithmisproposed.Asimpleyetef cientmotioncontentclassi erbasedonerrordescentrate(EDR)isdevelopedforthesearchpatternsswitchingdecision.

Therestofthepaperisorganizedasfollows.SectionIIgivesanoverviewonthevariousmotioncontentclassi ers.EDRisdiscussedinSectionIII.TheproposedSPSalgorithmbasedonEDRisdescribedinSectionIV.ExperimentalresultsaregiveninSectionV,whileSectionVIgivestheconclusions.

II.MOTIONCONTENTCLASSIFIER

AnadaptiveMEalgorithmcanselectbetweensearchpat-ternsorsearchstrategiesfordifferentmotioncontents.Themotioncontentofablockcanbeclassi edbyamotioncontentclassi er.Varioustypesofmotioncontentclassi cationhavebeenproposed.

A.ZeroMotionContentClassi er

Zeromotioncontentblocks,i.e.,theblockswithzeromotionvectors(ZMVs),existinmostvideosequences[4].Ifablockisclassi edasazeromotionblock,subsequentmotionsearchcanbeskipped.Someearlyterminationalgorithmscomparethedistortionofablockatthezeromotionpointwithathreshold.Thethresholdvaluecanbeprede nedbasedB.GeometricMotionContentClassi er

TheN3SSuseseightmoresearchpointsinitsinitialsearchcomparedwith3SS.Theinitialsearchpatterncanbeconsideredasthegeometricmotioncontentclassi erofN3SS.Iftheminimumdistortionpositionisnearthewindowcenter,theblockisclassi edasasmallmotionblockandaverycompactsearchpatternsimilartothatofBBGDSis

1051-8215/$25.00©2009IEEE

!!!! A Search Patterns Switching Algorithm for Block Motion Estimation

usedforthesubsequentsearch.Otherwise,N3SSemploysthecoarse-to- nesearchusedin3SStosearchthelargeMVs.

SimilartoN3SS,theef cientthree-stepsearch(E3SS)[11]usesitsinitialsearchpatternasthemotioncontentclassi er.Eithersmalldiamondsearch(SDS)or3SSwillbeselectedforsubsequentsearchaccordingtothemotioncontentclassi cation.Adaptivedouble-layeredinitialsearchpatternalgorithm[12]alsousestheinitialsearchpatternas

algorithms,themotioncontentclassi cationusingpredictedMVinformationcanremovethetemporalandspatialredun-dancybetweenblocks.However,motioncontentclassi cationusingMVpredictionrequiresmuchmoredatastorageandcomputationaloverhead.

A-TDBalgorithmproposedin[15]usesanothermotioncontentclassi ercalledpredictedpro tlist,whichisasortedlistofthesearchcenterdistortionsofalltheblocksinaframe.Experimentalresultsshowthatthepredictedpro tlistisrobust.However,thestorageandsortingoverheadofthelistincreasesthecomplexityoftheclassi cationprocess.

III.ERRORDESCENTRATE

Bytheunimodalerrorsurfaceassumption,blockdistortionmonotonicallydecreasestowardstheglobalminimum.Itcanbefurtherassumedthataglobalminimumpointhasagreatereffectonitsnearbyerrorsurfacethantheerrorsurfacefurtherawayfromit.Thise …… 此处隐藏：21443字，全部文档内容请下载后查看。喜欢就下载吧 ……