Scale&Affine Invariant Interest Point Detectors.

InternationalJournalofComputerVision60(1),63–86,2004c
2004KluwerAcademicPublishers.ManufacturedinTheNetherlands.Scale&AffineInvariantInterestPointDetectorsKRYSTIANMIKOLAJCZYKANDCORDELIASCHMIDINRIARhne-AlpesGRAVIR-CNRS,655av.del’Europe,38330Montbonnot,[e-mail]@inrialpes.frReceivedJanuary3,2003;RevisedSeptember24,2003;AcceptedJanuary22,2004Abstract.Inthispaperweproposeanovelapproachfordetectinginterestpointsinvarianttoscaleandaffinetransformations.Ourscaleandaffineinvariantdetectorsarebasedonthefollowingrecentresults:(1)InterestpointsextractedwiththeHarrisdetectorcanbeadaptedtoaffinetransformationsandgiverepeatableresults(geometricallystable).(2)Thecharacteristicscaleofalocalstructureisindicatedbyalocalextremumoverscaleofnormalizedderivatives(theLaplacian).(3)Theaffineshapeofapointneighborhoodisestimatedbasedonthesecondmomentmatrix.Ourscaleinvariantdetectorcomputesamulti-scalerepresentationfortheHarrisinterestpointdetectorandthenselectspointsatwhichalocalmeasure(theLaplacian)ismaximaloverscales.Thisprovidesasetofdistinctivepointswhichareinvarianttoscale,rotationandtranslationaswellasrobusttoilluminationchangesandlimitedchangesofviewpoint.Thecharacteristicscaledeterminesascaleinvariantregionforeachpoint.Weextendthescaleinvariantdetectortoaffineinvariancebyestimatingtheaffineshapeofapointneighborhood.Aniterativealgorithmmodifieslocation,scaleandneighborhoodofeachpointandconvergestoaffineinvariantpoints.Thismethodcandealwithsignificantaffinetransformationsincludinglargescalechanges.Thecharacteristicscaleandtheaffineshapeofneighborhooddetermineanaffineinvariantregionforeachpoint.Wepresentacomparativeevaluationofdifferentdetectorsandshowthatourapproachprovidesbetterresultsthanexistingmethods.Theperformanceofourdetectorisalsoconfirmedbyexcellentmatchingresults;theimageisdescribedbyasetofscale/affineinvariantdescriptorscomputedontheregionsassociatedwithourpoints.Keywords:interestpoints,localfeatures,scaleinvariance,affineinvariance,matching,recognition1.IntroductionLocalfeatureshavebeenshowntobewellsuitedtomatchingandrecognitionaswellastomanyotherap-plicationsastheyarerobusttoocclusion,backgroundclutterandothercontentchanges.Thedifficultyistoobtaininvariancetoviewingconditions.Differentsolu-tionstothisproblemhavebeendevelopedoverthepastfewyearsandarereviewedinSection1.1.Theseap-proachesfirstdetectfeaturesandthencomputeasetofdescriptorsforthesefeatures.Inthecaseofsignificanttransformations,featuredetectionhastobeadaptedtothetransformation,asatleastasubsetofthefea-turesmustbepresentinbothimagesinordertoallowforcorrespondences.Featureswhichhaveprovedtobeparticularlyappropriateareinterestpoints.How-ever,theHarrisinterestpointdetectorisnotinvari-anttoscaleandaffinetransformations(Schmidetal.,2000).InthispaperwegiveadetaileddescriptionofascaleandanaffineinvariantinterestpointdetectorintroducedinMikolajczykandSchmid(2001,2002).OurapproachcombinestheHarrisdetectorwiththeLaplacian-basedscaleselection.TheHarris-Laplacedetectoristhenextendedtodealwithsignificantaffinetransformations.Previousdetectorspartiallyhandletheproblemofaffineinvariancesincethey64MikolajczykandSchmidassumethatthelocalizationandscalearenotaffectedbyanaffinetransformationofthelocalimagestruc-tures.Theproposedimprovementsresultinbetterre-peatabilityandaccuracyofinterestpoints.Moreover,thescaleinvariantHarris-Laplaceapproachdetectsdif-ferentregionsthantheDoGdetector(Lowe,1999).Thelatteronedetectsmainlyblobs,whereastheHarrisde-tectorrespondstocornersandhighlytexturedpoints,hencethesedetectorsextractcomplementaryfeaturesinimages.Ifthescalechangebetweenimagesisknown,wecanadapttheHarrisdetectortothescalechange(Dufournaudetal.,2000)andwethenobtainpoints,forwhichthelocalizationandscaleperfectlyreflecttherealscalechangebetweentwoimages.Ifthescalechangebetweenimagesisunknown,asimplewaytodealwithscalechangesistoextractpointsatseveralscalesandtouseallthesepointstorepresentanim-age.Theproblemwithamulti-scaleapproachisthatingeneralalocalimagestructureispresentinacertainrangeofscales.Thepointsarethendetectedateachscalewithinthisrange.Asaconsequence,therearemanypoints,whichrepresentthesamestructure,butthelocationandthescaleofthepointsisslightlydiffer-ent.Theunnecessarilyhighnumberofpointsincreasestheprobabilityofmismatchesandthecomplexityofthematchingalgorithms.Inthiscase,efficientmethodsforrejectingthefalsematchesandforverifyingtheresultsarenecessary.Ourscaleinvariantapproachsolvesthisproblembyselectingthepointsinthemulti-scalerepresentationwhicharepresentatcharacteristicscales.Localex-tremaoverscaleofnormalizedderivativesindicatethepresenceofcharacteristiclocalstructures(Lindeberg,1998).HereweusetheLaplacian-of-Gaussiantose-lectpointslocalizedatmaximainscale-space.Thisdetectorcandealwithsignificantscalechanges,aspre-sentedinSection2.Toobtainaffineinvariantpoints,weadapttheshapeofthepointneighborhood.Theaffineshapeisdeterminedbythesecondmomentma-trix(LindebergandGarding,1997).Wethenobtainatrulyaffineinvariantimagedescriptionwhichgivesstable/repeatableresul