initializediscuz

AnError-TolerantApproximateMatchingAlgorithmforAttributedPlanarGraphsandItsApplicationtoFingerprintClassicationMichelNeuhausandHorstBunkeDepartmentofComputerScience,UniversityofBernNeubr¨uckstrasse10,CH-3012Bern,Switzerland{mneuhaus,bunke}@iam.
unibe.
chAbstract.
Grapheditdistanceisapowerfulerror-tolerantsimilaritymeasureforgraphs.
Forpatternrecognitionproblemsinvolvinglargegraphs,however,thehighcomputationalcomplexitymakesitsometimesimpossibletoapplyeditdistancealgorithms.
Inthepresentpaperweproposeanecientalgorithmforeditdistancecomputationofplanargraphs.
Givengraphsembeddedintheplane,weiterativelymatchsmallsubgraphsbylocallyoptimizingstructuralcorrespondences.
Eventuallyweobtainavalideditpathandhenceanupperboundoftheeditdistance.
Todemonstratetheeciencyofourapproach,weapplytheproposedalgorithmtotheproblemofngerprintclassication.
1IntroductionInrecentyearsgraphshavebeenrecognizedasapowerfulconcepttorepresentstructuralpatterns.
Similaritymeasuresforgraphsthatarebasedonanexactstructuralcorrespondencesuchasgraphisomorphismandmaximumcommonsubgraphareoftenelegantandquiteecient[1–3].
Forrealapplications,how-ever,itisoftendiculttondagraphrepresentationthatdealssucientlywellwithstructuralvariationsbetweengraphsfromthesameclass.
Graphmatchingproceduresthatallowforsuchstructuralvariations,so-callederror-tolerantal-gorithms,havebeenintroducedwiththedevelopmentofthegrapheditdistance[4,5].
Theeditdistanceofgraphsiscomputedbydeterminingtheleastcostlywaytoeditonegraphintoanother,givenanunderlyingsetofeditoperationsongraphsandtheircosts.
Duetotheenormouscomputationalcomplexityofthematchingproblemforgeneralgraphs,anumberofauthorshavestudiedspecialclassesofgraphs,suchastrees,bounded-valencegraphs,andgraphswithuniquenodelabels[6–8].
Inthepresentpaperwefocusontheproblemofecientlymatchinglargeattributedplanargraphsinthecontextoftheeditdistanceframework.
Planargraphsareinterestinginmanyapplicationsinvolvingimages,becausecommongraphrepresentationsextractedfromanimageareplanar.
Awell-knownexampleisregionadjacencygraphs[9].
InSection2ofthispaperthegrapheditdistanceterminologyisintroducedandinSection3theproposedapproximatedistancealgorithmforplanargraphsA.
Fredetal.
(Eds.
):SSPR&SPR2004,LNCS3138,pp.
180–189,2004.
cSpringer-VerlagBerlinHeidelberg2004AnError-TolerantApproximateMatchingAlgorithm181isdescribed.
Next,inSection4,wedemonstratehowplanargraphmatchingcanbeappliedtothengerprintclassicationproblemandpresentexperimentalresults.
Finally,conclusionsareprovidedinSection5.
2GraphEditDistanceGrapheditdistanceisanerror-tolerantsimilaritymeasureforgraphs[4,5].
Structuralvariationsbetweengraphsaremodeledwithasetofeditoperationssuchasnodeinsertion,nodedeletion,nodesubstitution,edgeinsertion,edgedeletion,andedgesubstitution.
Thekeyconceptistodescribestructuraldier-enceswiththesequenceofeditoperationsthatbestexplainthevariations.
Forthispurposeitiscommontoassigncoststoeditoperationssuchthattheyreectthestrengthofthecorrespondingdistortion.
Theeditdistanced(G,G)oftwographsGandGisthendenedasthecostoftheleastexpensiveeditpaththattransformsGintoG.
Theoretically,everynodeofGcouldbematchedtoeverynodeofG,aseditoperationsaredenedsuchthattheyareabletocorrectanystructuralerror,andastraight-forwardpruningcriterion(suchastheoneforgraphisomorphism)doesnotexist.
Hence,itiseasytoobservethatthecom-putationalcomplexityofthegrapheditdistancealgorithmisexponentialinthenumberofnodesinvolved.
Nonetheless,forsmallgraphsithasprovenapowerfulgraphsimilaritymeasure[9,10].
Butforlargegraphsitbecomescomputationallyinfeasibleduetoitshighrunningtimeandmemorycomplexity.
3ApproximatePlanarGraphEditDistanceInordertoovercomethedicultiesarisingfromthehighcomputationalcom-plexity,weproposeanapproximate,butecientalgorithmforthecomputationoftheeditdistanceforattributedplanargraphs.
Inthefollowingweassumethatourdatagraphsareprovidedwithaplanarembedding,thatis,adrawingofthegraphintheplanesuchthatnoneofitsedgesintersect.
AnexampleisshowninFig.
1.
Incontrasttoexactgrapheditdistancecomputation,whichdenesthedistanceintermsoftheleastexpensiveofalleditpaths,werestrictthenumberofpossibleeditoperationsanddeterminetheleastexpensivememberofasmallersetofcandidateeditpaths.
Thissetofcandidatepathsisobtainedinthecourseofaprocessthatembedsthegraphsunderconsiderationintheplane.
Ifthecandidategenerationprocessproducesaneditpaththatisclosethetheoptimalpath,theplanareditdistancewillapproximatethegrapheditdistancewell.
Forthedescriptionofthegenerationprocessofthecandidatepathsweneedthefollowingdenition.
Theneighborhoodofanodeuinagraphisdenedasthesubgraphconsistingofnodeu,allnodesconnectedtou,andalledgesbetweenthesenodes.
Moreformally,ifwedenoteagraphbyG=(V,E,α,β),whereVisthesetofnodes,Ethesetofdirectededges,α:V→LVthenodelabelingfunction,andβ:E→LEtheedgelabelingfunction,theneighborhoodN(u)ofuinGisdenedastheinducedsubgraphN(u)=(Vu,Eu,αu,βu)ofG,where182MichelNeuhausandHorstBunkea)b)Fig.
1.
Illustrationofa)aplanargraphandb)thesamegraphembeddedintheplaneVu={u}∪{v∈V|(v,u)∈Eor(u,v)∈E}Eu=E∩(Vu*Vu)αu=α|VUβu=β|EU.
AnillustrationofaneighborhoodisshowninFig.
2.
Notethattheembeddingoftheplanargraphispreservedintheneighborhood,thatis,thereisanorderdenedonthenodesconnectedtou.
uua)b)Fig.
2.
a)Planargraphandb)graphwithmarkedneighborhoodofuInordertoinitializethegenerationofacandidatepathintheprocessofmatchinggraphsGandG,aseedsubstitutionu→uhastobechosen,whereuisanodefromGanduanodefromG.
NextanoptimalmatchingfromsubgraphN(u)tosubgraphN(u)(wheresymbolNreferstographGandsymbolNtographG)basedontheunderlyingsetofeditoperationsistobedetermined.
Allnewsubstitutionsthatoccurinthismatchingaremarkedforfurtherprocessing.
Inconsecutivestepstheneighborhoodsbelongingtounprocessedsubstitutionsareprocessedinthesamemanner,wheresubstitutionsthatwerepreviouslyobtainedarepreservedinsubsequentneighborhoodmatchings.
Thematchingbeginswiththeseedneighborhoodandisiterativelyexpandedacrossthetwographs.
Theresultofthisprocedureisavalideditpathfromthersttothesecondgraph.
ThealgorithmisoutlinedinTable1.
AnError-TolerantApproximateMatchingAlgorithm183Table1.
PlanareditdistancealgorithmInput:TwoplanargraphsG=(V,E,α,β)andG=(V,E,α,β)tobematched.
Output:AmatchingbetweenGandGandthecorrespondingeditdistance,d(G,G)0.
Determineseedsubstitutionu0→u01.
Addseedsubstitutionu0→u0totheFIFOqueueQ2.
Fetchnextsubstitutionu→ufromQ3.
MatchneighborhoodN(u)toneighborhoodN(u)4.
Addnewsubstitutionsoccurringinstep3toQ5.
IfQisnotempty,gotostep26.
DeleteallunprocessednodesandedgesinbothGandGLetusconsiderstep3ofthealgorithm,theneighborhoodmatching,moreclosely.
Aneighborhoodconsistsofacenternode,asetofadjacentnodes,andedgesbetweenthesenodes.
Thesetofadjacentnodescanbeconsideredanor-deredsequenceofnodesduetotheplanarembeddingoftheneighborhood.
Inordertoobtainsuchanodesequence,werandomlystartatanadjacentnodeandtraverseallnodesinaclockwisemanner.
Insteadofregardinganeighborhoodasagraphtobematched,wecanrepresentaneighborhoodasanorderednodesequenceandmatchtwoneighborhoodssimplybyndinganoptimalnodealign-ment.
Withthisrestrictionweassumethattheoptimalneighborhoodmatchingpreservestheorderingofthenodesadjacenttothecenternode.
Thenodealign-mentcanbeperformedwithacyclicstringmatchingalgorithm[11–15],wherethesequenceofnodesisregardedasastringandthestringeditoperationcostsarederivedfromthecorrespondinggrapheditoperationcosts.
Ifweconsidergraphswithaboundedvalenceofv,thisproceduretakesO(v2).
ThealgorithmterminatesafterO(n)loops,wherendenotesthenumberofnodesinthegraphs.
Thecomputationalcomplexityofstringmatchingcanfurtherbereducedbypre-servingpreviouslymatchednodes.
Ifweconsiderastringsubstitutionu→u,werequirethatitsoperationcostsamounttozeroifu→uhasoccurredpre-viously,toinnityifasubstitutionu→vorv→uwithu=vandu=vhasoccurredpreviously,andtographeditoperationcostsc(u→u)otherwise.
Thismeansthatthepresenteditpathmustneverbeviolatedbynewlyaddededitoperations.
Theoptimalityoftheneighborhoodmatchingisdeterminedwithrespecttotheoriginalgrapheditoperations.
Neweditoperationsmatchingpreviouslyob-tainedoperationsareaddedtotheeditpathineveryneighborhoodmatching.
Whenthealgorithmterminates,thegenerationprocessyieldsavalideditpath.
Theapproximatedistancevalueisthereforeanupperboundofthetruegrapheditdistance.
Sincetheresultingeditpathstronglydependsontheseedsub-stitution,wesuggesttouseseveralplanardistancecomputationswithdierentseedsubstitutionsandchoosetheonethatreturnstheminimummatchingcosts.
Promisingseedsubstitutioncandidatescanforinstancebefoundclosetothebarycenteroftheplanarembeddinginbothgraphsormaybedeterminedwithalocalgraphmatching.
Ifknowledgeoftheunderlyingapplicationisavailable,itmayalsobeutilizedtondseedsubstitutioncandidates.
184MichelNeuhausandHorstBunke4ApplicationtoFingerprintClassicationFingerprintrecognitiontaskscancoarslybedividedintoverication(one-to-onematching),identication(one-to-manymatching),andclassication.
Fingerprintclassicationreferstotheprocessofassigningngerprintstoclasseswithsimilarcharacteristics.
Alargenumberofngerprintclassicationapproacheshavebeenreportedintheliterature,includingrule-based[16,17],syntactic[18],statistical[19],andneural-network-based[20]algorithms.
Structuralpatternrecognitionseemstobeparticularlywellsuitedtotheclassicationproblem,asngerprintanalysisnaturallyinvolvesthecomparisonofridgeandvalleystructures.
Forinstance,MaioandMaltoni[9]segmenttheorientationeldofridgelinesintohomogeneousregionsandconverttheseintoaregionadjacencygraph.
Theclas-sicationisthenperformedwithaneditdistancealgorithm.
Duetothenatureofthesegmentationprocess,theresultinggraphsareguaranteedtocontainatmosttennodes.
Marcialisetal.
[21]describehowtoimproveclassicationresultsbyfusingthisstructuralalgorithmwithastatisticalclassicationalgorithm.
Inthepresentpaper,weproposetouselargergraphsforthedescriptionoftheorientationeld.
Insteadofsegmentingtheorientationeld,wecombineorien-tationvectorsinawindowofconstantsizeandrepresentthemasasinglenode.
Inthefollowing,thegraphextractionandclassicationprocedureisdescribedindetail.
ExperimentalresultsarereportedinSection5.
Inourngerprintexperimentsweuseasubsetof450ngerprintsfromtheNIST-4database[22].
Thisdatabaseconsistsof2000pairsofgrayscalenger-printimagesthatareclassiedintooneoftheclassesarch,tentedarch,leftloop,rightloop,andwhorl.
AnexampleofawhorlimageisdepictedinFig.
3a.
Theimagebackgroundissegmentedfromtheforegroundbycomputingthegrayscalevarianceinawindowaroundeachpixel.
Thepixelsthatexhibitavariancelowerthanathresholdareconsideredbackground.
ForeachpixelwethenestimatethediscretegradientofthegrayscalesurfacebyapplyingaSobeloperatorintheverticalandhorizontaldirection.
AfterasmoothingprocessweobtainaridgeorientationeldasillustratedinFig.
3b.
Thenwerepresenteachpixelinawin-dowasagraphnodewithoutattributes.
Fromeverynodeanedgeisgeneratedinthosetwo,outofeight,possibledirectionsthatbestmatchthevectororthog-onaltotheaveragewindowgradient.
Asinglediscreteattributeγ∈{1,2,8}isattachedtoeveryedgerepresentingtheorientationoftheedge.
Thesizeoftheresultinggraphdependsonthesizeofthepixelwindow.
InFig.
3csuchagraphisillustrated.
The450ngerprintgraphsfromtheNIST-4subsetcontainanaverageof174nodesand193edgespergraphataresolutionof32*32pixelsperwindow.
Weuseasimpleeditcostfunctionthatassignsconstantcostspntonodeinsertionsanddeletions,andconstantcostspetoedgeinsertionsanddeletions.
Asnodesareunlabeled,thereisnocostfornodesubstitutions,andedgesub-stitutioncostsaresetproportionaltothedistanceofthetwoinvolvedangles,d(γ,γ)=min{(γγ)mod8,(γγ)mod8},forγ,γ∈{1,2,8}.
Theratiooftheedgeinsertionanddeletionpenaltypeandtheedgesubstitutioncostps,i.
e.
2pe/ps,determineswhenanedgedeletionfollowedbyanedgeinsertionislessexpensivethananedgesubstitution.
AnError-TolerantApproximateMatchingAlgorithm185a)b)c)Fig.
3.
a)NIST-4whorlimagef0011,b)averagedridgeorientationeld,andc)ori-entationgraphTable2.
Runningtimeofexactgrapheditdistancealgorithm(GED,1run)andplanareditdistanceapproximation(PED,50runs)—emptyentriesindicatefailureduetolackofmemoryNodesGEDPED5<1s<1s7<1s<1s99s1s12-1s20-1s30-2s42-5s169-15sThengerprintclassicationisperformedbyevaluatingdistancesofun-knowninputgraphstolabeledprototypegraphs.
Weadoptanearest-neighborparadigmandclassifygraphsaccordingtoamaximumsimilarity,orminimumeditdistance,criterionwithrespecttotheprototypegraphs.
Notethat,withthisclassicationprocedure,weratherintendtodemonstratetheapplicabilityoftheapproximateplanareditdistancealgorithmthanprovideathoroughlyoptimizedngerprintclassicationsystem.
5ExperimentalResultsToevaluatetherunningtimeoftheapproximatealgorithmforplanareditdis-tancecomputation,weperformthestandardgrapheditdistancecomputationandtheplanareditdistancecomputationforthesamepairofgraphs.
Thestan-dardgrapheditdistanceisadeterministicalgorithmthatyieldstheexactdis-tancevalue,whereastheplanareditdistanceapproximationrequiresseveralrunstobecarriedout.
TheresultsofseveraldistancecomputationsforpairsofngerprintgraphsareshowninTable2.
Forsmallgraphswithlessthan10nodesandedges,theexactgrapheditdistancecomputationiscomputationally186MichelNeuhausandHorstBunke45050055060065070075080085012345678910DistanceGraphsamplesFig.
4.
Exactgrapheditdistance(lowercurve)andapproximatedplanareditdistance(uppercurve)for10graphsandsubgraphswith10nodesfeasible.
Forlargergraphs,however,theeditdistancesearchtreeexceedsthememorycapacityofourtestingmachine(1024MB).
Theplanareditdistance,ontheotherhand,providesaresultforeverytestedgraphpair,takingonlyafewsecondsforall50runs.
Duetomemorycontraints,theexacteditdistancecannotbecomputedforlargegraphs.
Itisthereforediculttodirectlyevaluatetheaccuracyoftheapproximationalgorithm.
Ifwedeletesomenodesfromagivengraph,however,weobtainapairofgraphsforwhichaminimumcosteditpathisknown,sothatwecaneasilycomputetheexacteditdistancebetweenthesegraphs.
Theplanareditdistanceapproximationforthesegraphsiscomputedintheusualmannerwithoututilizinganyknowledgeofthespecialformofthesamplegraphs.
Inourrstexperiment,wedeleteallbutthe10nodeslocatedclosesttothebarycenteroftheplanarembeddingfromangerprintgraphandmatchtheresultinggraphwiththeoriginalone.
Inthesecondexperiment,weusethesameproceduretoconstructsubgraphswith100nodes.
Theresulting(known)exacteditdistanceandthe(computed)approximatedistanceoftherst10pairsofgraphsfromNIST-4areillustratedinFig.
4.
Asexpectedtheapproximationyieldsanupperboundoftheexactdistance.
Interestinglyenough,theapproximationseemstocloselyfollowtheexactdistanceuptoanadditiveconstant.
Ifwecomputetheempiriccorrelationcoecientoftheapproximatedandtheexactdistanceoftherst100graphsfromNIST-4,weobtainacoecientofr=0.
99forthesubgraphswith10nodesandr=0.
85forthesubgraphswith100nodes.
Thisresultindicatesthattheapproximatedandtheexactdistancearestronglycorrelatedinalinearway.
InFig.
5,thecorrelationcanclearlybeobserved.
Aregressionanalysisoftheexactdistancexandtheapproximationyaccordingtothelinearmodely=αx+βyieldsaslopeofα=0.
99andanosetofβ=93forsubgraphswith10nodes,andaslopeofα=1.
10andanosetofβ=803forsubgraphswith100nodes.
Aslopeofapproximatelyα=1isequivalenttothereducedlinearregressionmodely=x+β.
Weconcludethatthedierenceoftheapproximationandtheexactdistance(asillustratedinFig.
4)isalmostAnError-TolerantApproximateMatchingAlgorithm187450500550600650700750500550600650700750800850ExactgrapheditdistanceApproximatedplanareditdistance50100150200250300350850900950100010501100115012001250ExactgrapheditdistanceApproximatedplanareditdistanceFig.
5.
Exactgrapheditdistanceandapproximatedplanareditdistanceforsubgraphswith10nodes(left)andsubgraphswith100nodes(right)Table3.
FingerprintclassicationrecognitionratesperclassClassRecognitionrateArch62.
5%Tentedarch72.
5%Leftloop77.
5%Rightloop85%Whorl90%constantandthattheapproximationthereforereectsthestructuralsimilarityoftheunderlyinggraphswell.
Inourthirdexperimentwetesttheapplicabilityoftheproposedplanareditdistancetotheproblemofngerprintclassication.
Theexperimentproceedsasfollows.
Foreachoftheveclassesarch,tentedarch,leftloop,rightloop,andwhorlwerandomlyselect40inputgraphstobeclassiedandanother50graphsrepresentingtherespectivengerprintcategory.
Thisresultsinatestsetofsize200andatraining,orprototype,setofsize250graphs.
Bycomputingtheap-proximateplanareditdistance,weobtainasimilarityvaluebetweeneachinputgraphandeachprototypeandclassifytheinputgraphwithanearest-neighborclassier.
TherecognitionratesweachievewiththisprocedureareshowninTable3.
Evaluatingsomemisclassiedsamples,wenotethattherecognitioner-rorsmainlyoccuronpairsofngerprintsfromdierentclassesthathaveahighsubjectivesimilarity.
6ConclusionsInthepresentpaperweproposeanecientapproximateeditdistancealgorithmforplanargraphs.
Thegraphmatchingisperformedbyiterativelyextendingpairsofmatchingsubgraphsoftwogivengraphs.
Ouralgorithmgeneratesasingleeditpathbetweentwographsbylocallyoptimizingthestructurecor-188MichelNeuhausandHorstBunkerespondence.
Theoptimizationisaccomplishedwithanecientcyclicstringmatchingalgorithm.
WeevaluatetheplanareditdistanceonngerprintgraphsextractedfromgrayscalengerprintimagesfromtheNIST-4database.
Theeditdistanceap-proximationisveryfastcomparedtoastandardeditdistancecomputation.
Theapproximateddistancevaluesseemtobesucientlyaccurateforthemeasure-mentofthestructuralsimilarityofgraphs.
Particularlyforlargergraphswithmorethan100nodesandedges,theplanareditdistanceoersagoodtradeobetweenrunningtimeandaccuracy.
Inthefutureweintendtostudytheinu-enceofthesetofprototypicalstructuresontheclassicationperformanceandevaluatethengerprintclassicationsystemonlargerdatasets.
AcknowledgmentThisresearchwassupportedbytheSwissNationalScienceFoundationNCCRprogram"InteractiveMultimodalInformationManagement(IM)2"intheIndi-vidualProject"MultimediaInformationAccessandContentProtection".
References1.
Bunke,H.
,Shearer,K.
:Agraphdistancemetricbasedonthemaximalcommonsubgraph.
PatternRecognitionLetters19(1998)255–2592.
Fernandez,M.
L.
,Valiente,G.
:Agraphdistancemetriccombiningmaximumcom-monsubgraphandminimumcommonsupergraph.
PatternRecognitionLetters22(2001)753–7583.
Wallis,W.
,Shoubridge,P.
,Kraetzl,M.
,Ray,D.
:Graphdistancesusinggraphunion.
PatternRecognitionLetters22(2001)701–7044.
Sanfeliu,A.
,Fu,K.
:Adistancemeasurebetweenattributedrelationalgraphsforpatternrecognition.
IEEETransactionsonSystems,Man,andCybernetics13(1983)353–3635.
Messmer,B.
,Bunke,H.
:Anewalgorithmforerror-tolerantsubgraphisomorphismdetection.
IEEETransactionsonPatternAnalysisandMachineIntelligence20(1998)493–5046.
Hopcroft,J.
,Wong,J.
:Lineartimealgorithmforisomorphismofplanargraphs.
In:Proc.
6thAnnualACMSymposiumonTheoryofComputing.
(1974)172–1847.
Luks,E.
:Isomorphismofgraphsofboundedvalencecanbetestedinploynomialtime.
JournalofComputerandSystemsSciences25(1982)42–658.
Dickinson,P.
,Bunke,H.
,Dadej,A.
,Kraetzl,M.
:Ongraphswithuniquenodelabels.
InHancock,E.
,Vento,M.
,eds.
:Proc.
4thInt.
WorkshoponGraphBasedRepresentationsinPatternRecognition.
LNCS2726(2003)13–239.
Lumini,A.
,Maio,D.
,Maltoni,D.
:Inexactgraphmatchingforngerprintclassi-cation.
MachineGraphicsandVision,SpecialIssueonGraphTransformationsinPatternGenerationandCAD8(1999)231–24810.
Ambauen,R.
,Fischer,S.
,Bunke,H.
:Grapheditdistancewithnodesplittingandmerginganditsapplicationtodiatomidentication.
InHancock,E.
,Vento,M.
,eds.
:Proc.
4thInt.
WorkshoponGraphBasedRepresentationsinPatternRecognition.
LNCS2726(2003)95–106AnError-TolerantApproximateMatchingAlgorithm18911.
Bunke,H.
,B¨uhler,U.
:Applicationsofapproximatestringmatchingto2Dshaperecognition.
PatternRecognition26(1993)1797–181212.
Llados,J.
,Mart,E.
,Villanueva,J.
:Symbolrecognitionbyerror-tolerantsub-graphmatchingbetweenregionadjacencygraphs.
IEEETransactionsonPatternAnalysisandMachineIntelligence23(2001)1137–114313.
Peris,G.
,Marzal,A.
:Fastcycliceditdistancecomputationwithweightededitcostsinclassication.
InKasturi,R.
,Laurendeau,D.
,Suen,C.
,eds.
:Proc.
16thInt.
Conf.
onPatternRecognition.
Volume4.
(2002)184–18714.
Mollineda,R.
,Vidal,E.
,Casacuberta,F.
:Awindowedweightedapproachforapproximatecyclicstringmatching.
InKasturi,R.
,Laurendeau,D.
,Suen,C.
,eds.
:Proc.
16thInt.
Conf.
onPatternRecognition.
(2002)188–19115.
Robles-Kelly,A.
,Hancock,E.
:Stringeditdistance,randomwalksandgraphmatching.
Int.
JournalofPatternRecognitionandArticialIntelligence(2004)toappear.
16.
Kawagoe,M.
,Tojo,A.
:Fingerprintpatternclassication.
PatternRecognition17(1984)295–30317.
Karu,K.
,Jain,A.
:Fingerprintclassication.
PatternRecognition29(1996)389–40418.
Rao,K.
,Balck,K.
:Typeclassicationofngerprints:Asyntacticapproach.
IEEETransactionsonPatternAnalysisandMachineIntelligence2(1980)223–23119.
Jain,A.
,Prabhakar,S.
,Hong,L.
:Amultichannelapproachtongerprintclas-sication.
IEEETransactionsonPatternAnalysisandMachineIntelligence21(1999)348–35920.
Wilson,C.
,Candela,G.
,Watson,C.
:Neuralnetworkngerprintclassication.
JournalofArticialNeuralNetworks1(1994)203–22821.
Marcialis,G.
,Roli,F.
,Serrau,A.
:Fusionofstatisticalandstructuralngerprintclassiers.
InKittler,J.
,Nixon,M.
,eds.
:4thInt.
Conf.
Audio-andVideo-BasedBiometricPersonAuthentication.
LNCS2688(2003)310–31722.
Watson,C.
,Wilson,C.
:NISTSpecialDatabase4.
FingerprintDatabase.
(1992)