资源描述：
《图像匹配是NP完全问题外文文献翻译.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、ElasticimagematchingAbstractOnefundamentalprobleminimagerecognitionistoestablishtheresemblanceoftwoimages.Thiscanbedonebysearchingthebestpixeltopixelmappingtakingintoaccountmonotonicityandcontinuityconstraints.WeshowthatthisproblemisNP-completebyreductionfrom3-SAT,thusgivingevidencethattheknow
2、nexponentialtimealgorithmsarejustified,butapproximationalgorithmsorsimplificationsarenecessary.Keywords:Elasticimagematching;Two-dimensionalwarping;NP-completeness1.IntroductionInimagerecognition,acommonproblemistomatchtwogivenimages,e.g.whencomparinganobservedimagetogivenreferences.Inthatpro-
3、cess,elasticimagematching,two-dimensional(2D-)warping(UchidaandSakoe,1998)orsimilartypesofinvariantmethods(Keysersetal.,2000)canbeused.Forthispurpose,wecandefinecostfunctionsdependingonthedistortionintroducedinthematchingandsearchforthebestmatchingwithrespecttoagivencostfunction.Inthispaper,we
4、showthatitisanalgorithmicallyhardproblemtodecidewhetheramatchingbetweentwoimagesexistswithcostsbelowagiventhreshold.WeshowthattheproblemimagematchingisNP-completebymeansofareductionfrom3-SAT,whichisacommonmethodofdemonstratingaproblemtobeintrinsicallyhard(GareyandJohnson,1979).Thisresultshowst
5、heinherentcomputationaldifficultiesinthistypeofimagecomparison,whileinterestinglythesameproblemissolvablefor1Dsequencesinpolynomialtime,e.g.thedynamictimewarpingprobleminspeechrecognition(seee.g.Neyetal.,1992).Thishasthefollowingimplications:researcherswhoareinterestedinanexactsolutiontothispr
6、oblemcannothopetofindapolynomialtimealgorithm,unlessP=NP.Furthermore,onecanconcludethatexponentialtimealgorithmsaspresentedandextendedbyUchidaandSakoe(1998,1999a,b,2000a,b)maybejustifiedforsomeimagematchingapplications.Ontheotherhandthisshowsthatthoseinterestedinfasteralgorithms––e.g.forpatter
7、nrecognitionpurposes––arerightinsearchingforsub-optimalsolutions.Onemethodtodothisistherestrictiontolocaloptimizationsorlinearapproximationsofglobaltransformationsaspresentedin(Keysersetal.,2000).Anotherpossibilityistouseheuristicapproa
