图像匹配是NP完全问题外文文献翻译

ElasticimagematchingAbstractOnefundamentalprobleminimagerecognitionistoestablishtheresemblanceoftwoimages.Thiscanbedonebysearchingthebestpixeltopixelmappingtakingintoaccountmonotonicityandcontinuityconstraints.WeshowthatthisproblemisNP-completebyreductionfrom3-SAT,thusgivingevidencethattheknownexponentialtimealgorithmsarejustified,butapproximationalgorithmsorsimplificationsarenecessary.Keywords:Elasticimagematching;Two-dimensionalwarping;NP-completeness1.IntroductionInimagerecognition,acommonproblemistomatchtwogivenimages,e.g.whencomparinganobservedimagetogivenreferences.Inthatpro-cess,elasticimagematching,two-dimensional(2D-)warping(UchidaandSakoe,1998)orsimilartypesofinvariantmethods(Keysersetal.,2000)canbeused.Forthispurpose,wecandefinecostfunctionsdependingonthedistortionintroducedinthematchingandsearchforthebestmatchingwithrespecttoagivencostfunction.Inthispaper,weshowthatitisanalgorithmicallyhardproblemtodecidewhetheramatchingbetweentwoimagesexistswithcostsbelowagiventhreshold.WeshowthattheproblemimagematchingisNP-completebymeansofareductionfrom3-SAT,whichisacommonmethodofdemonstratingaproblemtobeintrinsicallyhard(GareyandJohnson,1979).Thisresultshowstheinherentcomputationaldifficultiesinthistypeofimagecomparison,whileinterestinglythesameproblemissolvablefor1Dsequencesinpolynomialtime,e.g.thedynamictimewarpingprobleminspeechrecognition(seee.g.Neyetal.,1992).Thishasthefollowingimplications:researcherswhoareinterestedinanexactsolutiontothisproblemcannothopetofindapolynomialtimealgorithm,unlessP=NP.Furthermore,onecanconcludethatexponentialtimealgorithmsaspresentedandextendedbyUchidaandSakoe(1998,1999a,b,2000a,b)maybejustifiedforsomeimagematchingapplications.Ontheotherhandthisshowsthatthoseinterestedinfasteralgorithms––e.g.forpatternrecognitionpurposes––arerightinsearchingforsub-optimalsolutions.Onemethodtodothisistherestrictiontolocaloptimizationsorlinearapproximationsofglobaltransformationsaspresentedin(Keysersetal.,2000).Anotherpossibilityistouseheuristicapproacheslikesimulatedannealingorgeneticalgorithmstofindanapproximatesolution.Furthermore,methodslikebeamsearcharepromisingcandidates,astheseareusedsuccessfullyinspeechrecognition,althoughlinguisticdecodingisalsoanNP-completeproblem(CasacubertaanddelaHiguera,1999).2.ImagematchingAmongthevarietiesofmatchingalgorithms,wechoosetheonepresentedbyUchidaandSakoe(1998)asastartingpointtoformalizetheproblemimagematching.Lettheimagesbegivenas(withoutlossofgenerality)squaregridsofsizeM×Mwithgrayvalues(respectivelynodelabels)fromafinitealphabet&={1，…，G}.Todefinetheproblem,twodistancefunctionsareneeded,oneactingongrayvaluesgd：&×&→N,measuringthematchingrayvalues,andoneactingondisplacementdifferencesdd:Z×Z→N,measuringthedistortionintroducedbythematching.Forthesedistancefunctionsweassumethattheyaremonotonousfunctions(computableinpolynomialtime)ofthecommonlyusedsquaredEuclid-eandistance,i.edg(g1,g2)=f1(||g1-g2||²)anddd(z)=f2(||z||²)monotonouslyincreasing.Nowwecallthefollowingoptimizationproblemtheimagematchingproblem(letµ={1，…M}).Instance:Thepair(A;B)oftwoimagesAandBofsizeM×M.Solution:Amappingfunctionf:µ×µ→µ×µ.Measure:c（A,B,f）=),(),(jifijgBAd),(ji+}1,{1,),()))0,1(),(())0,1(),(((Mjidjifjifd}1,{1,),(Mji+1}-M,{1,),()))1,0(),(())1,0(),(((jidjifjifd1}-M,{1,),(jiGoal:minfc(A,B,f).Inotherwords,theproblemistofindthemappingfromAontoBthatminimizesthedistancebetweenthemappedgrayvaluestogetherwithameasureforthedistortionintroducedbythemapping.Here,thedistortionismeasuredbythedeviationfromtheidentitymappinginthetwodimensions.Theidentitymappingfulfillsf(i,j)=(i,j),andtherefore，f((i,j)+(x,y))=f(i,j)+(x,y)ThecorrespondingdecisionproblemisfixedbythefollowingQuestion:Givenaninstanceofimagematchingandacostc′,doesthereexistamappingfsuchthatc(A,B,f)≤c′?Inthedefinitionoftheproblemsomecaremustbetakenconcerningthedistancefunctions.Forexample,ifeitheroneofthedistancefunctionsisaconstantfunction,theproblemisclearlyinP(fordgconstant,theminimumisgivenbytheidentitymappingandforddconstant,theminimumcanbedeterminedbysortingallpossiblematchingforeachpixelbygrayvaluecostandmappingtooneofthepixelswithminimumcost).Butthesespecialcasesarenotthoseweareconcernedwithinimagematchingingeneral.WechoosethematchingproblemofUchidaandSakoe(1998)tocompletethedefinitionoftheproblem.Here,themappingfunctionsarerestrictedbycontinuityandmonotonicityconstraints:thedeviationsfromtheidentitymappingmaylocallybeatmostonepixel(i.e.limitedtotheeight-neighborhoodwithsquaredEuclideandistancelessthanorequalto2).Thiscanbeformalizedinthisapproachbychoosingthefunctionsf1,f2ase.g.f1=id，f2(x)=step(x):=.2,)10(,2,0xGxMM3.Reductionfrom3-SAT3-SATisaverywell-knownNP-completeproblem(GareyandJohnson,1979),where3-SATisdefinedasfollows:Instance:CollectionofclausesC={C1，···,CK}onasetofvariablesX={x1，···xL}suchthateachckconsistsof3literalsfork=1，···K.Eachliteralisavariableorthenegationofavariable.Question:IsthereatruthassignmentforXwhichsatisfieseachclauseck,k=1，···K?ThedependencygraphD（Ф）correspondin