Fast Contour Matching Using Approximate Earth Mover’s Distance.pdf

《Fast Contour Matching Using Approximate Earth Mover’s Distance.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、FastContourMatchingUsingApproximateEarthMover’sDistanceKristenGraumanandTrevorDarrellComputerScienceandArtificialIntelligenceLaboratoryMassachusettsInstituteofTechnologyCambridge,MA,02139Abstractpolynomialcomplexityforeachdatabasememberagainstthequeryshap

2、e.Hierarchicalsearchmethods,pruning,orWeightedgraphmatchingisagoodwaytoalignapairofthetriangleinequalitymaybeemployed,yetquerytimesshapesrepresentedbyasetofdescriptivelocalfeatures;arestilllinearinthesizeofthedatabaseintheworstcase,thesetofcorrespondence

3、sproducedbytheminimumcostandindividualcomparisonsmaintaintheirhighcomplexitymatchingbetweentwoshapesfeaturesoftenrevealshowregardless.similartheshapesare.However,duetothecomplexityofToaddressthecomputationalcomplexityofcurrentcomputingtheexactminimumcost

4、matching,previousal-correspondence-basedshapematchingalgorithms,wepro-gorithmscouldonlyrunefficientlywhenusingalimitedposeacontourmatchingalgorithmthatincorporatesre-numberoffeaturespershape,andcouldnotscaletoper-centlydevelopedapproximationtechniquesande

5、nablesfastformretrievalsfromlargedatabases.Wepresentacon-shape-basedsimilarityretrievalfromlargedatabases.Wetourmatchingalgorithmthatquicklycomputesthemin-treatcontourmatchingasagraphmatchingproblem,andimumweightmatchingbetweensetsofdescriptivelocaluseth

6、eEarthMover’sDistance(EMD)–theminimumcostfeaturesusingarecentlyintroducedlow-distortionembed-thatisnecessarytotransformoneweightedpointsetintodingoftheEarthMoversDistance(EMD)intoanormedanother–asametricofsimilarity.Weembedtheminimumspace.Givenanovelembe

7、ddedcontour,thenearestneigh-weightmatchingofcontourfeaturesintoL1viatheEMDborsinadatabaseofembeddedcontoursareretrievedinembeddingof[11],andthenemployapproximatenearestsublineartimeviaapproximatenearestneighborssearchneighbor(NN)searchtoretrievetheshapes

8、thataremostwithLocality-SensitiveHashing(LSH).Wedemonstrateoursimilartoanovelquery.Theembeddingstepalonere-shapematchingmethodonadatabaseof136,500imagesofducesthecomplexityofcomputingalow-costcorrespon-humanfigures.Ourmetho