图像识别中英文对照外文翻译文献.docx
- 文档编号:8988513
- 上传时间:2023-05-16
- 格式:DOCX
- 页数:30
- 大小:308.94KB
图像识别中英文对照外文翻译文献.docx
《图像识别中英文对照外文翻译文献.docx》由会员分享,可在线阅读,更多相关《图像识别中英文对照外文翻译文献.docx(30页珍藏版)》请在冰点文库上搜索。
中英文对照外文翻译文献
Elasticimagematching
Abstract
Onefundamentalprobleminimagerecognitionistoestablishtheresemblanceoftwoimages.Thiscanbedonebysearchingthebestpixeltopixelmappingtakingintoaccountmonotonicityandcontinuityconstraints.WeshowthatthisproblemisNP-completebyreductionfrom3-SAT,thusgivingevidencethattheknownexponentialtimealgorithmsarejustified,butapproximationalgorithmsorsimplificationsarenecessary.
Keywords:
Elasticimagematching;Two-dimensionalwarping;NP-completeness
1.Introduction
Inimagerecognition,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.Imagematching
Amongthevarietiesofmatchingalgorithms,wechoosetheonepresentedbyUchidaandSakoe(1998)as astartingpointtoformalizetheproblemimagematching.Lettheimagesbegivenas(withoutlossofgenerality)squaregridsofsizeM×Mwithgrayvalues(respectivelynodelabels)fromafinitealphabet&={1,…,G}.Todefinetheproblem,twodistancefunctionsareneeded,oneactingongrayvalues :
&×&→N,measuringthematchingrayvalues,andoneactingondisplacementdifferencesd:
Z×Z→N,measuringthedistortionintroducedbythematching.Forthesedistancefunctionsweassumethattheyaremonotonousfunctions(computableinpolynomialtime)ofthecommonlyusedsquaredEuclid-eandistance,i.ed(g,g)=f(||g-g||²)andd(z)=f(||z||²)monotonouslyincreasing.Nowwecallthefollowingoptimizationproblemtheimagematchingproblem(letµ={1,…M}).
Instance:
Thepair(A;B)oftwoimagesAandBofsizeM×M.
Solution:
Amappingfunctionf:
µ×µ→µ×µ.
Measure:
c(A,B,f)=
+
+
Goal:
minc(A,B,f).
Inotherwords,theproblemistofindthemappingfromAontoBthatminimizesthedistancebetweenthemappedgrayvaluestogetherwithameasureforthedistortionintroducedbythemapping.Here,thedistortionismeasuredbythedeviationfromtheidentitymappinginthetwodimensions.Theidentitymappingfulfillsf(i,j)=(i,j),andtherefore,f((i,j)+(x,y))=f(i,j)+(x,y)
Thecorrespondingdecisionproblemisfixedbythefollowing
Question:
Givenaninstanceofimagematchingandacostc′,doesthereexistamappingfsuchthatc(A,B,f)≤c′?
Inthedefinitionoftheproblemsomecaremustbetakenconcerningthedistancefunctions.Forexample,ifeitheroneofthedistancefunctionsisaconstantfunction,theproblemisclearlyinP(fordconstant,theminimumisgivenbytheidentitymappingandfordconstant,theminimumcanbedeterminedbysortingallpossiblematchingforeachpixelbygrayvaluecostandmappingtooneofthepixelswithminimumcost).Butthesespecialcasesarenotthoseweareconcernedwithinimage
matchingingeneral.WechoosethematchingproblemofUchidaandSakoe(1998)tocompletethedefinitionoftheproblem.Here,themappingfunctionsarerestrictedbycontinuityandmonotonicityconstraints:
thedeviationsfromtheidentitymappingmaylocallybeatmostonepixel(i.e.limitedtotheeight-neighborhoodwithsquaredEuclideandistancelessthanorequalto2).Thiscanbeformalizedinthisapproachbychoosingthefunctionsf,f ase.g.
f=id,f(x)=step(x):
=
3.Reductionfrom3-SAT
3-SATisaverywell-knownNP-completeproblem(GareyandJohnson,1979),where3-SATisdefinedasfollows:
Instance:
CollectionofclausesC={C,···,C}onasetofvariablesX={x,···x}suchthateachcconsistsof3literalsfork=1,···K.Eachliteralisavariableorthenegationofavariable.
Question:
IsthereatruthassignmentforXwhichsatisfieseachclausec,k=1,···K?
ThedependencygraphD(Ф)correspondingtoaninstanceФof3-SATisdefinedtobethebipartitegraphwhoseindependentsetsareformedbythesetofclausesCandthesetofvariablesX.Twoverticescandxareadjacentiffcinvolvesxor.
Givenany3-SATformulaU,weshowhowtoconstructinpolynomialtimeanequivalentimagematching probleml(Ф)=(A(Ф),B(Ф));.Thetwoimagesofl(Ф)aresimilaraccordingtothecostfunction(i.e.f:
c(A(Ф),B(Ф),f)≤0)ifftheformulaФissatisfiable.Weperformthereductionfrom3-SATusingthefollowingsteps:
•FromtheformulaФweconstructthedependencygraphD(Ф).
•ThedependencygraphD(Ф)isdrawnintheplane.
•ThedrawingofD(Ф)isrefinedtodepictthelogicalbehaviourofФ,yieldingtwoimages(A(Ф),B(Ф)).
Forthis,weusethreetypesofcomponents:
onecomponenttorepresentvariablesofФ,onecomponenttorepresentclausesofФ,andcomponentswhichactasinterfacesbetweentheformertwotypes.Beforewegivetheformalreduction,weintroducethesecomponents.
3.1.Basiccomponents
Forthereductionfrom3-SATweneedfivecomponentsfromwhichwewillconstructthein-stancesforimagematching,givenaBooleanformulain3-DNF,respectivelyitsgraph.Thefivecomponentsarethebuildingblocksneededforthegraphdrawingandwillbeintroducedinthefollowing,namelytherepresentationsofconnectors,crossings,variables,andclauses.Theconnectorsrepresenttheedgesandhavetwovarieties,straightconnectorsandcornerconnectors.Eachofthecomponentsconsistsoftwoparts,oneforimageAandoneforimageB,whereblankpixelsareconsideredtobeofthe‘background’color.
Wewilldepictpossiblemappingsinthefollowingusingarrowsindicatingthedirectionofdisplacement(wheredisplacementswithintheeight-neighborhoodofapixelaretheonlycasesconsidered).Blanksquaresrepresentmappingtotherespectivecounterpartinthesecondimage.Forexample,thefollowingdisplacementsofneighboringpixelscanbeusedwithzerocost:
Ontheotherhand,thefollowingdisplacementsresultincostsgreaterthanzero:
Fig.1showsthefirstcomponent,thestraightconnectorcomponent,whichconsistsofalineoftwodifferentinterchangingcolors,heredenotedbythetwosymbols◇and□.Giventhattheoutsidepixelsaremappedtotheirrespectivecounterpartsandtheconnectoriscontinuedinfinitely,therearetwopossiblewaysinwhichthecoloredpixelscanbemapped,namelytotheleft(i.e.f(2,j)=(2,j-1))ortotheright(i.e.f(2,j)=(2,j+1)),wherethebackgroundpixelshavedifferentpossibilitiesforthemapping,notinfluencingthemainpropertyoftheconnector.Thisproperty,whichjustifiesthename‘connector’,isthefollowing:
Itisnotpossibletofindamapping,whichyieldszerocostwheretherelativedisplacementsoftheconnectorpixelsarenotequal,i.e.onealwayshasf(2,j)-(2,j)=f(2,j')-(2,j'),whichcaneasilybeobservedbyinductionoverj'.Thatis,givenaninitialdisplacementofonepixel(whichwillbe±1inthiscontext),theremainingendoftheconnectorhasthesamedisplacementifoverallcostsofthemappingarezero.Giventhispropertyandthedirectionofaconnector,whichwedefinetobedirectedfromvariabletoclause,wecandefinethestateoftheconnectorascarryingthe‘true’truthvalue,ifthedisplacementis1pixelinthedirectionoftheconnectorandascarryingthe‘false’ truthvalue,ifthedisplacementis-1pixelinthedirectionoftheconnector.Thispropertythenensuresthatthetruthvaluetransmittedbytheconnectorcannotchangeatmappingsofzerocost.
Image A imageB
mapping 1 mapping2
Fig.1.Thestraightconnectorcomponentwithtwopossiblezerocostmappings.
Fordrawingofarbitrarygraphs,clearlyonealsoneedscorners,whicharerepresentedinFig.2.Byconsideringallpossibledisplacementswhichguaranteeoverallcostzero,onecanobservethatthecornercomponentalsoensuresthebasicconnectorproperty.Forexample,considerthefirstdepictedmapping,whichhaszerocost.Ontheotherhand,thesecondmappingshows,thatit
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 图像 识别 中英文 对照 外文 翻译 文献