IEEETRANSACTIONSONIMAGEPROCESSING,VOL.9,NO.2,FEBRUARY2000
本页已使用福昕阅读器进行编辑。福昕软件(C)2005-2007,版权所有,287仅供试用。
II.OBSERVATIONS
Fundamentallyspeaking,thesearchpattern'sshapeandsizeex-ploitedinthefastalgorithmjointlydeterminenotonlyitssearchspeedbutalsoresultedperformance.Blockdistortions(orblock-matchingerrors)formanerrorsurfaceoverthesearchwindow,andtheglobalminimumpointcorrespondstothemotionvectorwherethebestmatching(ortheleasterror)incurs.Sincetheerrorsurfaceisusuallynotmonotonic,multiplelocalminimumpointsgenerallyexistinthesearchwindowespeciallyforthoseimagesequenceswithlargemotioncontent.Therefore,searchingwithasmallsearchpattern,suchastheoneusedinBBGDS[8]withsizeof323,isquitelikelytobetrappedintoalocalminimumforthosevideosequenceswithlargemotioncontent.Ontheotherhand,alargesearchpatternwithsizeof929andsparsecheckingpointsasexploitedinthefirststepofTSSismostlikelytomisleadthesearchpathtoawrongdirectionandhencemissestheoptimumpoint.
Sincethedistributionoftheglobalminimumpointsinreal-worldvideosequencesiscenteredatthepositionofzeromotion(i.e.,searchwindowcenter)[6],thecenter-biasedNTSSalgorithm,whichisanim-provedversionofTSS,tendstoachievemuchsuperiorperformancewithfewernumberofsearchpointsonaverage.However,NTSSlosestheregularityandsimplicityofTSStosomeextent.Usingamoderatesearchpatternwithfixedsizeof525,4SS[7]obtainssimilarperfor-mancecomparedtothatofNTSS.NotethatbothNTSSand4SSutilizetheoverlappingofcheckingpointsbetweenadjacentsearchstepstore-ducethecomputationalcomplexityfurther.However,4SSstillrequirestotest17checkingpointsforastationaryblock,whichismuchmorethantheninecheckingpointsusedbyBBGDSinthesamecase.ItisworthtomentionthatexceptBBGDS,theotherthreefastBMA’s,i.e.,TSS,NTSSand4SS,commonlyrefrainthesearchwindowsizetobe15215astheirsearchingframeworksrequire.
TableIIdocumentsthemotionvectordistributionprobabilitieswithincertaindistancesfromthesearchwindowcenterbyexploitingtheFSalgorithmtosixcommonlyusedtestimagesequences(refertoTableI)basedonthemean-squareerror(MSE)matchingcriterion.Thepredictedframeiscontiguoustothepreviousoriginalframeintheexperiments.AsindicatedinTableII,about52.76%to98.70%ofthemotionvectorsareenclosedinacircularsupportwitharadiumof2pelsandcenteredonthepositionofzeromotion.Second,theblockdisplacementofreal-worldvideosequencescouldbeinanydirection,butmainlyinhorizontalandverticaldirections(e.g.,camerapanning).Basedonthesetwocrucialobservations,thesearchpoints(markedby“×”inFig.1)incurredwithinthecirclewitharadiumof2pels(thedottedlineinFig.1)arethemostappropriateonestobechosentocomposethesearchpattern,andanewdiamondsearch(DS)algorithmisdevelopedasdescribedinthefollowingsection.
ANewDiamondSearchAlgorithmforFastBlock-Matching
MotionEstimation
ShanZhuandKai-KuangMa
Abstract—Basedonthestudyofmotionvectordistributionfromsev-eralcommonlyusedtestimagesequences,anewdiamondsearch(DS)al-gorithmforfastblock-matchingmotionestimation(BMME)isproposedinthispaper.SimulationresultsdemonstratethattheproposedDSalgo-rithmgreatlyoutperformsthewell-knownthree-stepsearch(TSS)algo-rithm.Comparedwiththenewthree-stepsearch(NTSS)algorithm,theDSalgorithmachievescloseperformancebutrequireslesscomputationbyupto22%onaverage.ExperimentalresultsalsoshowthattheDSalgorithmisbetterthanrecentlyproposedfour-stepsearch(4SS)andblock-basedgra-dientdescentsearch(BBGDS),intermsofmean-squareerrorperformanceandrequirednumberofsearchpoints.
IndexTerms—Block-matchingalgorithm,diamondsearch,H.261,H.263,motionestimation,MPEG,videocoding,videocompression.
I.INTRODUCTION
Duetolimitedchannelbandwidthandstringentrequirementsofreal-timevideoplayback,videocodingisanindispensableprocessformanyvisualcommunicationapplicationsandalwaysrequiresaveryhighcompressionratio.Thelargeamountoftemporalcor-relation,orso-calledtemporalredundancyfromthecompressionviewpoint,

betweenadjacentframesinavideosequence,requirestobeproperlyidentifiedandeliminatedtoachievethisobjective.Aneffectiveandpopularmethodtoreducethetemporalredundancy,calledblock-matchingmotionestimation(BMME),hasbeenwidelyadoptedinvariousvideocodingstandards,suchasCCITT(nowITU-T)H.261,H.263,MPEG-1,MPEG-2,andMPEG-4[1],andinanymotion-compensatedvideocodingtechnique.Therefore,fastandaccurateblock-basedsearchtechniqueishighlydesirabletoassuremuchreducedprocessingdelaywhilemaintaininggoodreconstructedimagequality.
Byexhaustivelytestingallthecandidateblockswithinthesearchwindow,fullsearch(FS)algorithmgivestheglobaloptimumsolution(i.e.,themiimummatchingerrorpointoverthesearchwindow)tothemotionestimation,whileasubstantialamountofcomputationalloadismanyfastblock-matchingal-forexample,2-Dlogarithmic(TSS)[3],conjugatedirectionnewthree-stepsearch(NTSS)gradientdescentsearch(BBGDS)[8],etc.ThesefastBMA’sexploitdifferentsearchpatternsandsearchstrategiesforfindingtheoptimummotionvectorwithdras-ticallyreducednumberofsearchpointsascomparedwiththeFSalgo-rithm.
Inthispaper,weproposeasimple,robustandefficientfastBMMEalgorithm,calleddiamondsearch(DS)[9],[10],afterobservingthefollowingfacts.
III.DIAMONDSEARCHALGORITHM
TheproposedDSalgorithmemploystwosearchpatternsasillus-tratedinFig.2,whicharederivedfromthecrosses(×)inFig.1.Thefirstpattern,calledlargediamondsearchpattern(LDSP),comprisesninecheckingpointsfromwhicheightpointssurroundthecenteronetocomposeadiamondshape(5).Thesecondpatternconsistingoffivecheckingpointsformsasmallerdiamondshape,calledsmalldiamondsearchpattern(SDSP).
InthesearchingprocedureoftheDSalgorithm,LDSPisrepeatedlyuseduntilthestepinwhichtheminimumblockdistortion(MBD)oc-cursatthecenterpoint.ThesearchpatternisthenswitchedfromLDSPtoSDSPasreachingtothefinalsearchstage.Amongthefivechecking
ManuscriptreceivedNovember11,1997;revisedFebruary26,1999.Thispaperwaspresentedinpartatthe1stIEEEInternationalConferenceonIn-formation,Communications,andSignalProcessing(ICICS),Singapore,Sept.9–12,1997.TheassociateeditorcoordinatingthereviewofthismanuscriptandapprovingitforpublicationwasProf.StevenD.Blostein.
S.ZhuiswithV-BitsVideoEngineeringDept.,CiscoSystems,Inc.,SanJose,CA,95134USA.
K.-K.MaiswiththeSchoolofElectricalandElectronicEngineering,NanyangTechnologicalUniversity,Singapore(e-mail:ekkma@ntu.edu.sg).PublisherItemIdentifierS1057-7149(00)01253-7.
1057–7149/00$10.00©2000IEEE
6, NO. 3, JUNE 1996 313 Express Letters A Novel Four-Step Search Algorithm for Fast Block Motion Estimation Lai-Man Po and Wing-Chung Ma Abstract-...
A novel cross-diamond search algorithm for fast block motion estimation (CDS 02.11)_信息与通信_工程科技_专业资料。A novel cross-diamond search algorithm...
A fast motion estimation algorithm for mobile communications_专业资料。The limitation of processing power, battery life and memory capacity of portable ...
A fast motion estimation (ME) algorithm is ...(JVT) encoder that performs a variable-block ME...(OTS) [6], and the new diamond search [7]....
A FAST PARAMETER ESTIMATION ALGORITHM FOR POLYPHASE CODED CW SIGNALS_专业资料。V18N.O2l. O1 JURLOFEETRISCNA)ONA LCONC(HI Jnay21 aur0 1 A ...
and/or explicit smoothness constraints on the block-matching algorithm. ...I. I NTRODUCTION OTION estimation (ME) has a vital role in video coding...
A novel adjustable multiple cross-hexagonal search algorithm for fast block motion estimation 隐藏>> 维普资讯 http://www.cqvip.com Xee 1Jhjn nvcA0788:...
An_Algorithm_for_Least-Squares_Estimation_of_Nonlinear_Parameters1_数学_自然科学_专业资料。今日推荐 180份文档 CET四六级高分通关宝典...
Index Terms—Adaptive search pattern, block-matching algorithm, diamond search, fast motion estimation, rood pattern, spatial correlation, video compression, ...
Fast Sub-Pixel Motion Estimation Algorithm For H.264_专业资料 暂无评价
热门文档