surf算法

1SURF:SpeededUpRobustFeaturesInthissection,theSURFdetector-descriptorschemeisdiscussedindetail.Firstthealgorithmisanalysedfromatheoreticalstandpointtoprovideadetailedoverviewofhowandwhyitworks.Nextthedesignanddevelopmentchoicesfortheimplementationofthelibraryarediscussedandjustied.Duringtheimplementationofthelibrary,itwasfoundthatsomeofthenerdetailsofthealgorithmhadbeenomittedoroverlooked,soSection1.5servestomakecleartheconceptswhicharenotexplicitlydenedintheSURFpaper[1].1.1IntegralImagesMuchoftheperformanceincreaseinSURFcanbeattributedtotheuseofanintermediateimagerepresentationknownasthe\IntegralImage[18].Theintegralimageiscomputedrapidlyfromaninputimageandisusedtospeedupthecalculationofanyuprightrectangulararea.GivenaninputimageIandapoint(x;y)theintegralimageIPiscalculatedbythesumofthevaluesbetweenthepointandtheorigin.Formallythiscanbedenedbytheformula:IP(x;y)=ixXi=0jyXj=0I(x;y)(1)Figure1:AreacomputationusingintegralimagesUsingtheintegralimage,thetaskofcalculatingtheareaofanuprightrectangularregionisreducedfouroperations.IfweconsiderarectangleboundedbyverticesA,B,CandDasinFigure1,thesumofpixelintensitiesiscalculatedby:X=A+D(C+B)(2)Sincecomputationtimeisinvarianttochangeinsizethisapproachisparticularlyusefulwhenlargeareasarerequired.SURFmakesgooduseofthispropertytoperformfastconvolutionsofvaryingsizeboxltersatnearconstanttime.1.2Fast-HessianDetector1.2.1TheHessianTheSURFdetectorisbasedonthedeterminantoftheHessianmatrix.InordertomotivatetheuseoftheHessian,weconsideracontinuousfunctionoftwovariablessuchthatthevalueofthefunctionat(x;y)isgivenbyf(x;y).TheHessianmatrix,H,isthematrixofpartialderivatesofthefunctionf.H(f(x;y))=@2f@x2@2f@x@y@2f@x@y@2f@y2#(3)Thedeterminantofthismatrix,knownasthediscriminant,iscalculatedby:det(H)=@2f@x2@2f@y2@2f@x@y2(4)Thevalueofthediscriminantisusedtoclassifythemaximaandminimaofthefunctionbythesecondorderderivativetest.SincethedeterminantistheproductofeigenvaluesoftheHessianwecanclassifythepointsbasedonthesignoftheresult.Ifthedeterminantisnegativethentheeigenvalueshavedierentsignsandhencethepointisnotalocalextremum;ifitispositivetheneitherbotheigenvaluesarepositiveorbotharenegativeandineithercasethepointisclassiedasanextremum.Translatingthistheorytoworkwithimagesratherthanacontinuousfunctionisafairlytrivialtask.Firstwereplacethefunctionvaluesf(x;y)bytheimagepixelintensi-tiesI(x;y).Nextwerequireamethodtocalculatethesecondorderpartialderivativesoftheimage.AsdescribedinSection??wecancalculatederivativesbyconvolutionwithanappropriatekernel.InthecaseofSURFthesecondorderscalenormalisedGaussianisthechosenlterasitallowsforanalysisoverscalesaswellasspace(scale-spacetheoryisdiscussedfurtherlaterinthissection).WecanconstructkernelsfortheGaussianderiva-tivesinx,yandcombinedxydirectionsuchthatwecalculatethefourentriesoftheHessianmatrix.UseoftheGaussianallowsustovarytheamountofsmoothingduringtheconvolutionstagesothatthedeterminantiscalculatedatdierentscales.Further-more,sincetheGaussianisanisotropic(i.e.circularlysymmetric)function,convolutionwiththekernelallowsforrotationinvariance.WecannowcalculatetheHessianmatrix,H,asfunctionofbothspacex=(x;y)andscale.H(x;)=Lxx(x;)Lxy(x;)Lxy(x;)Lyy(x;)#;(5)HereLxx(x;)referstotheconvolutionofthesecondorderGaussianderivative@2g()@x2withtheimageatpointx=(x;y)andsimilarlyforLyyandLxy.ThesederivativesareknownasLaplacianofGaussians.WorkingfromthiswecancalculatethedeterminantoftheHessianforeachpixelintheimageandusethevaluetondinterestpoints.ThisvariationoftheHessiandetectorissimilartothatproposedbyBeaudet[2].Lowe[9]foundperformanceincreaseinapproximatingtheLaplacianofGaussiansbyadierenceofGaussians.Inasimiliarmanner,Bay[1]proposedanapproximationtotheLaplacianofGaussiansbyusingboxlterrepresentationsoftherespectivekernels.Figure2illustratesthesimilaritybetweenthediscretisedandcroppedkernelsandtheirboxltercounterparts.ConsiderableperformanceincreaseisfoundwhentheseltersareusedinconjunctionwiththeintegralimagedescribedinSection1.1.Toqauntifythedierencewecanconsiderthenumberofarrayaccessesandoperationsrequiredintheconvolution.Fora99lterwewouldrequire81arrayaccessesandoperationsfortheoriginalrealvaluedlterandonly8fortheboxlterrepresentation.Asthelterisincreasedinsize,thecomputationcostincreasessignicantlyfortheoriginalLaplacianwhilethecostfortheboxltersisindependentofsize.Figure2:LaplacianofGaussianApproximation.TopRow:ThediscretisedandcroppedsecondorderGaussianderivativesinthex,yandxy-directions.WerefertotheseasLxx,Lyy,Lxy.BottomRow:WeightedBoxlterapproximationsinthex,yandxy-directions.WerefertotheseasDxx,Dyy,DxyInFigure2theweightsappliedtoeachoftheltersectionsiskeptsimple.Theblackregionsareweightedwithavalueof1,thewhiteregionswithavalueof-1andtheremainingareasnotweightedatall.Simpleweightingallowsforrapidcalculationofareasbutinusingtheseweightsweneedtoaddressthedierenceinresponsevaluesbetweentheoriginalandapproximatedkernels.Bay[1]proposesthefollowingformulaasanaccurateapproximationfortheHessiandeterminantusingtheapproximatedGaussia