2009年sift算法文章 2009_Fast_approximate_nearest_neighbors_with_automatic_algorithm_configuration

FASTAPPROXIMATENEARESTNEIGHBORSWITHAUTOMATICALGORITHMCONFIGURATION

MariusMuja,DavidG.Lowe

ComputerScienceDepartment,UniversityofBritishColumbia,Vancouver,B.C.,Canada

mariusm@cs.ubc.ca,lowe@cs.ubc.ca

Keywords:Abstract:

nearest-neighborssearch,randomizedkd-trees,hierarchicalk-meanstree,clustering.

Formanycomputervisionproblems,themosttimeconsumingcomponentconsistsofnearestneighbormatch-inginhigh-dimensionalspaces.Therearenoknownexactalgorithmsforsolvingthesehigh-dimensionalproblemsthatarefasterthanlinearsearch.Approximatealgorithmsareknowntoprovidelargespeedupswithonlyminorlossinaccuracy,butmanysuchalgorithmshavebeenpublishedwithonlyminimalguidanceonselectinganalgorithmanditsparametersforanygivenproblem.Inthispaper,wedescribeasystemthatanswersthequestion,“Whatisthefastestapproximatenearest-neighboralgorithmformydata?”Oursystemwilltakeanygivendatasetanddesireddegreeofprecisionandusethesetoautomaticallydeterminethebestalgorithmandparametervalues.Wealsodescribeanewalgorithmthatappliesprioritysearchonhierarchicalk-meanstrees,whichwehavefoundtoprovidethebestknownperformanceonmanydatasets.Aftertestingarangeofalternatives,wehavefoundthatmultiplerandomizedk-dtreesprovidethebestperformanceforotherdatasets.Wearereleasingpublicdomaincodethatimplementstheseapproaches.Thislibraryprovidesaboutoneorderofmagnitudeimprovementinquerytimeoverthebestpreviouslyavailablesoftwareandprovidesfullyautomatedparameterselection.

1INTRODUCTION

Themostcomputationallyexpensivepartofmanycomputervisionalgorithmsconsistsofsearchingfortheclosestmatchestohigh-dimensionalvectors.Ex-amplesofsuchproblemsinclude ndingthebestmatchesforlocalimagefeaturesinlargedatasets(Lowe,2004;Philbinetal.,2007),clusteringlocalfeaturesintovisualwordsusingthek-meansorsim-ilaralgorithms(SivicandZisserman,2003),orper-formingnormalizedcross-correlationtocompareim-agepatchesinlargedatasets(Torralbaetal.,2008).Thenearestneighborsearchproblemisalsoofmajorimportanceinmanyotherapplications,includingma-chinelearning,documentretrieval,datacompression,bioinformatics,anddataanalysis.

Wecande nethenearestneighborsearchprob-lemasfollows:givenasetofpointsP={p1,...,pn}inavectorspaceX,thesepointsmustbepreprocessedinsuchawaythatgivenanewquerypointq∈X, ndingthepointsinPthatarenearesttoqcanbeper-

formedef ciently.Inthispaper,wewillassumethatXisanEuclideanvectorspace,whichisappropriateformostproblemsincomputervision.Wewillde-scribepotentialextensionsofourapproachtogeneralmetricspaces,althoughthiswouldcomeatsomecostinef ciency.

Forhigh-dimensionalspaces,thereareoftennoknownalgorithmsfornearestneighborsearchthataremoreef cientthansimplelinearsearch.Aslin-earsearchistoocostlyformanyapplications,thishasgeneratedaninterestinalgorithmsthatperformapproximatenearestneighborsearch,inwhichnon-optimalneighborsaresometimesreturned.Suchap-proximatealgorithmscanbeordersofmagnitudefasterthanexactsearch,whilestillprovidingnear-optimalaccuracy.

Therehavebeenhundredsofpaperspublishedonalgorithmsforapproximatenearestneighborsearch,buttherehasbeenlittlesystematiccomparisontoguidethechoiceamongalgorithmsandsettheirinter-nalparameters.Onereasonforthisisthattherelative