文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > A_new_diamond_search_algorithm_for_fast_block-matching_motion_estimation_TIP2000
侵权投诉

A_new_diamond_search_algorithm_for_fast_block-matching_motion_estimation_TIP2000

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,

A_new_diamond_search_algorithm_for_fast_block-matching_motion_estimation_TIP2000

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

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email