资源描述：
PatternRecognitionChapter6,StructuralPatternRecognitionPatternRecognitionConcepts,sandApplicationsJ.P.MarquesdeSaSpringer,6StructuralPatternRecognition,6.1PatternPrimitives6.2StructuralRepresentations6.3SyntacticAnalysis6.4StructuralMatching,6.1PatternPrimitives,6.1.1SignalPrimitivesapiecewiselinearapproximationofasignalisbythemostpopularofsignaldecomposition.Setasignalsxthattheapproximatebyapiecewiselinearfunctionhxwithdsegments.Theapproximationerroris（6-1）whereanappropriatenorm,usuallytheChebychevnormortheEuclidiannorm,isusedtouatethedeviationsofsxjfromhixj.,,6.1.2ImagePrimitives,Imageprimitivescanbeobtainedthroughtheapplicationofalargevarietyofimageanalysistechniques,suchasimagesegmentation,edgedetection,contourfollowingandmedialaxistransation.,ChainCodeandTemplates,Figure6.1aOctalprimitivestopandtemplatesbottom;bBinaryimagewithcontourlinesegmentsaccordingtotheoctalprimitives,,Chaincodeconstitutesaneasywayofencodingatwo-dimensionalcurve,Itconsistsoffollowingthecurvefromaspecifiedstartingpointand,foreachlinesegment,connectingthegridpointsthatfallclosesttothecurve.Thegridpointconnectionsarethencodedaccordingtoasetofoctalprimitives..Classictemplatesarestartingfromthehighestverticalgridcellthatisnotempty,onecanfollowthecontourinaclockwisedirection,selectingthetemplatethatbestcorrespondswiththecurrentcontourcell.,Curvesegments,Imagesdescribedbycurvesegments,particularlylinesegments,canbeobtainedbyapplyingedgedetectorstothem.Theyareusuallycalledshapeprimitivesorimagesilhouetteprimitives.,,Figure6.2aImageofatanktoymodel;bImagecontoursdetectedbyanedgedetectionalgorithm,6.2StructuralRepresentations,6.2.1Strings6.2.2Graphs6.2.3Trees,6.2.1Strings,Astringisanorderedsequenceofsymbols,eachsymbolrepresentingaprimitive.AstringxisthenasequenceofsymbolsofTrepresentedasdefinetheconcatenationofstringsxala2...amandyb1b2...bnwithmsymbolsandnsymbols,respectively,anddenotethisoperationasxy,yieldingthestringwithmnsymbols,,,,（6-2）,,（6-3）,6.2.2Graphs,AgraphGisanorderedpair6-4whereN,thenodeset,isasetofnodes,andR,theedgeset,isasetofbinaryrelationsdefinedinNxN.TheelementsofRrepresentarcsoredgesconnectingnodesofN.AnarcofGisdenoteda,bwitha,b∈N.,,,,Figure6.3primitivesandrelationsusedtodescribecapitallettersaandlabelleddigraphsforthelettersRandEb.,6.2.3Trees,Atreeisanundirectedgraphwithnoclosedloopsacyclicgraphandwithaspecialnode,therootnode,within-degreeofzeroandeveryothernodewithout-degree≥1,excepttheterminalorleafnodes,whichhaveout-degreezero,,Figure6.4Primitivesaandrelationsbusedtodescribefurniture,,Figure6.5AcupboardaanditsdescriptiontreebusingtheprimitivesandrelationsofFigure6.4.,6.3SyntacticAnalysis,Syntacticanalysisistheapproachtostructuralpatternrecognitionbasedonthetheoryofallanguages.Theuseofgrammarstodescribepatternsisadvantageous,giventhewell-developedbodyofknowledgeinthisareaandthestandardizedwayonecanapplythesameapproachinmanydifferentcircumstances.,6.3.1StringGrammars,DefineaalstringgrammarasaquadrupleGT,N,P,STisasetofsymbols,calledterminalsymbols,correspondinginthecaseofthepatternstothesetofprimitives,alsocalledpatternalphabet.ThesetofstringsbuiltwiththeelementsofTisusuallydenotedT（6-5）AallanguageLisasubsetof,constitutedbystringsobeyingcertainrules.,,,2.Nisasetofclasssymbols,alsocallednon-terminalsymbols,i.e.,symbolsthatdenoteclassesofelementsofT.ThesetsTandNaredisjointedandtheirunion,constitutesthelanguagevocabulary.3.Pisasetofsyntacticrules,knownasproductionrules,usedtogeneratethestrings.EachruleisrepresentedasTheproductionruleα→β,read“αproducesβ“,meansthatanyoccurrenceofαinastringcanbesubstitutedbyβ.4.Sisaspecialparentclasssymbol,alsocalledstartingsymbol,usedtostartthegenerationofanystringwiththerulesofP.,,α→β,with,6-6b,6.3.2PictureDescriptionLanguage,Thisistheapproachofthepicturedescriptionlanguage,PDL,whichprovidesanadequaterepresentationoftwo-dimensionalpatterns.InPDLeachprimitivehastwoattachingpoints,tailandhead,whereitcanbelinkedtootherprimitives.ThesetofterminalsincludesfourbinaryoperatorsandoneunaryoperatorthatcanbeusedtojoinprimitivesasshowninTable6.1.,Table6.1.PDLoperatorsandtheirmeaning.,6.3.3GrammarTypes,ThefollowingrelationsexistforthesefourtypesofgrammarsG0G1G2G3.ThisiscalledtheChomskyhierarchy,namedafterNoamChomskywhosecontributiontotheallanguagetheorywascapital.,,,,,6.3.4StochasticGrammars,Astochasticgrammarisagrammarwhoseproductionruleshaveprobabilitiesassociatedwiththem,suchthatforeverysymbolαiproducingsymbolsβjthereareprobabilitiesPijsatisfyingTherefore,theprobabilitiesassociatedwiththesameleftsidesymbolofaproductionadduptoone.,,,with,,6-8,,Theprobabilityofx∈LG,Px︱G,iscomputedas1.Ifx∈LGisunambiguousandhasaderivationwithkrules,eachwithprobabilityPj,then2.Ifx∈LGisambiguousandhasldifferentderivationswithprobabilitiesPix︱G,then,,,,6-9a,,6-9b,,Figure6.8.AnECGsignal,zoomed4x,describedbyapiecewiseapproximationusingChebychevnormwithtolerance20,withsegmentslabelledusingslopethresholdsof5and22.,6.4StructuralMatching,6.4.1StringMatchingStringmatchingisbasedonasimilaritymeasurebetweentwostringsxandywithnandmsymbols,respectively,andisdefinedintermsofthenumberofelementaryeditoperationsthatarerequiredtotransthestringxintothestringy.Themostcommoneditoperationsare1.Substitutionofasymbolainxbyasymbolhiny;2.Insertionofasymbolainy;3.Deletionofasymbolainx.,,Consider,forexample,T﹛h,d,u﹜,xduuhandyhdhuh.Stringxcanbetransedintoyasfollows-inserthinxhduuh;-substituteuinxbyhinyhdhuh.Anotheralternativeis-substitutedinxbyhinyhuuh;-insertdinxhduuh;-substituteuinxbyhinyhdhuh.,Figure6.10.ComputationoftheLevenshteindistancebetweenxandy,usingunitarycostsforallelementaryeditoperations.Thedottedlinecorrespondstotheminimumcostpath.,6.4.2ProbabilisticRelaxationMatching,AssumethattherearenobjectsAithatwewanttolabelwithmlabelslk.Supposealsothatthelabelassignmentsoftheobjectsareinterdependent.Ourgoalistoobtainacompatibleassignmentoflabelstoobjects,measuredbyaprobabilityestimate,Pij,ofassigningljtoAi.Onewaytocombine,ateachiterationr,theincrementsforallobjectsAhandlabelslk,istoadduptheincrementsforallpossiblelabelsas,,6-18,,andaveragetheseincrementsforallobjectsxh≠xi6-19Thequantitiesqijarein[-1,1]andcanbeusedtoupdatethePij,satisfyingtheconstraintsthattheyarenonnegativeandadduptooneforeachobject,inthefollowingway6-20Themostimportantdecisionsonemustmakewhenapplyingprobabilisticrelaxationrelatetothechoiceofcompatibilitymeasuresandtheestimationofthe,,,,6.4.3DiscreteRelaxationMatching,Indiscreterelaxation,foreveryAhrelevanttoAi,theremustbeatleastonelabelk,suchthatcij;hklwithPhkl;Atsubsequentiterations,Pijremains1ifforeveryrelevantAhthereisanassignmentsuchthatcij;hkPhkl;otherwisePijbecomes0.Thisisequivalenttothefollowingula,,6-21,,Figure6.14.Discreterelaxationappliedtotwosimplesexamplesofcompatibleaandincompatiblebshapes.,6.4.4GraphandTreeMatching,ConsidertwographsortreesG1﹛N1,R1﹜andG2﹛N2,R2﹜,describingthestructuralrelationsoftwopatterns.AhomomorphismfromGItoG2isanyfunctionfestablishingacorrespondencebetweenthenodesofN1andthenodesofN2suchthatanypairofadjacentnodesinGIcorresponds,throughf,toadjacentnodesinN2.Leta,brepresenttwoadjacentnodesofN1.Thenahomomorphismfsatisfies,,6-22,,Figure6.15.Twodigraphswithtwohomomorphismsafla,f2b,f3c;bfla,f2c,f3d.,Figure6.16.MatchgraphforthetwographsshowninFigure6.15.Thehomomorphissareshownwithsolidline.,
展开阅读全文
