Systematic Methods for the

来源：意榕旅游网

IEEETRANSACTIONSONPATTERNANALYSISANDMACHINEINTELLIGENCE,VOL.24,NO.7,JULY2002905

SystematicMethodsforthe

ComputationoftheDirectionalFieldsandSingularPointsofFingerprints

AskerM.BazenandSabihH.Gerez

AbstractÐThefirstsubjectofthispaperistheestimationofahighresolutiondirectionalfieldoffingerprints.Traditionalmethodsarediscussedandanewmethod,basedonprincipalcomponentanalysis,isproposed.Themethodnotonlycomputesthedirectioninanypixellocation,butitscoherenceaswell.Itisproventhatthismethodprovidesexactlythesameresultsastheªaveragedsquare-gradientmethodºthatisknownfromliterature.Undoubtedly,theexistenceofacompletelydifferentequivalentsolutionincreasestheinsightintotheproblem'snature.Thesecondsubjectofthispaperissingularpointdetection.Averyefficientalgorithmisproposedthat

Âindexandprovidesaextractssingularpointsfromthehigh-resolutiondirectionalfield.ThealgorithmisbasedonthePoincare

consistentbinarydecisionthatisnotbasedonpostprocessingstepslikeapplyingathresholdonacontinuousresemblancemeasureforsingularpoints.Furthermore,amethodispresentedtoestimatetheorientationoftheextractedsingularpoints.Theaccuracyofthemethodsisillustratedbyexperimentsonalive-scannedfingerprintdatabase.

IndexTermsÐImageprocessing,fingerprintrecognition,directionalfield,orientationestimation,singularpointextraction,principalcomponentanalysis.

recognitionhasreceivedincreasinglymore

attentionduringthelastyears.Sincetheperformanceoffingerprintverificationsystemshasreachedasatisfactorylevelforapplicationsinvolvingsmalldatabases,thenextstepisthedevelopmentofalgorithmsforfingerprintidentificationsystemsthatcansearchrelativelylargedatabasesforamatchingfingerprint.Althoughotherapproachesarepossi-ble,like,forinstance,thehashingtechniqueintheminutiaedomain[1],thefirststepinanidentificationsystemisoftencontinuousclassificationoffingerprints[2],[3].Thisreducesthepartitionofthedatabasetobesearchedformatches.Tofacilitatehigh-performanceclassification,algorithmsforaccuratedirectionalfieldandsingular-pointestimationareneeded.

InFig.1a,afingerprintisdepicted.Theinformationcarryingfeaturesinafingerprintarethelinestructures,calledridgesandvalleys.Inthisfigure,theridgesareblackandthevalleysarewhite.Itispossibletoidentifytwolevelsofdetailinafingerprint.Thedirectionalfield(DF),showninFig.1b,describesthecoarsestructure,orbasicshape,ofafingerprint.Itisdefinedasthelocalorientationoftheridge-valleystructures.Theminutiaeprovidesthedetailsoftheridge-valleystructures,likeridge-endingsandbifurcations.Minutiaeare,forinstance,usedforfingerprintmatching,whichisaone-to-onecomparisonoftwofingerprints.

ThispaperfocusesonthedirectionalfieldoffingerprintsandmattersdirectlyrelatedtotheDF.TheDFis,inprinciple,

INGERPRINT

INTRODUCTION

perpendiculartothegradients.However,thegradientsareorientationsatpixelscale,whiletheDFdescribestheorientationoftheridge-valleystructures,whichisamuchcoarserscale.Therefore,theDFcanbederivedfromthegradientsbyperformingsomeaveragingoperationonthegradients,involvingpixelsinsomeneighborhood[4].ThisisillustratedinFig.2a,whichshowsthegradientsinapartofafingerprint,andFig.2b,whichshowstheaverageddirec-tionalfield.Whilethegradientsarenotallparallelbecauseoftheendpoint,thedirectionalfieldisbecauseoftheaveragingoperator.TheaveragingofgradientsinordertoobtaintheDFisthefirsttopicofthispaper.

TheestimationmethodthatisdescribedinthispaperenablestheapplicationofDF-relatedtasksthatrequireveryhighresolutionandaccurateDFs.Examplesofthesedemandingtechniquesare,forinstance,theaccurateªextractionofsingularpointsºasdiscussedinSection3andªhigh-performanceclassification.ºTogetherwiththeDF,thecoherencecanbeestimated.Thecoherenceisameasurethatindicateshowwellthegradientsarearepointinginthesamedirection.Anexampleofitsuseishigh-resolutionsegmentation[5],[6].

IntheDF,singularpoints(SPs)canbeidentified.Theextractionofthosesingularpointsisthesecondtopicofthispaper.SPsarethepointsinafingerprintwherethedirectionalfieldisdiscontinuous.Henry[7]definedtwotypesofsingularpoints,intermsoftheridge-valleystructures.Thecoreisthetopmostpointoftheinnermostcurvingridgeandadeltaisthecenteroftriangularregionswherethreedifferentdirectionflowsmeet.ThelocationsofthesingularpointsinanexamplefingerprintaregiveninFig.1c.Apartfromitslocation,anSPhasanorientation;thispaperalsoproposesanestimationmethodfortheorientationofSPs[8].

ThemostcommonuseofSPsisregistration,whichmeansthattheyareusedasreferencestolineuptwofingerprints.Anotherexampleoftheiruseisclassificationoffingerprints

.TheauthorsarewiththeUniversityofTwente,DepartmentofElectricalEngineering,POBox217,7500AE,Enschede,TheNetherlands.E-mail:{a.m.bazen,s.h.gerez}@el.utwente.nl.Manuscriptreceived25July2000;revised24Apr.2001;accepted8Dec.2001.

RecommendedforacceptancebyR.Kumar.

Forinformationonobtainingreprintsofthisarticle,pleasesende-mailto:tpami@computer.org,andreferenceIEEECSLogNumber112593.

0162-8828/02/$17.00ß2002IEEE

906IEEETRANSACTIONSONPATTERNANALYSISANDMACHINEINTELLIGENCE,VOL.24,NO.7,JULY2002

Fig.1.Examplesofafingerprint,itsdirectionalfieldanditssingularpoints:(a)fingerprint,(b)directionalfield,and(c)singularpoints.

Fig.2.Detailedareainafingerprint:(a)thegradientand(b)theaverageddirectionalfield.

intheHenryclasses[9].Theorientationofsingularpointscanbeusedformoreadvancedclassificationmethods,ortoinitializeflowlinesintheDF[9],[10],[11],[12].

Thispaperisorganizedasfollows:First,inSection2,theestimationoftheDFisdiscussed.InSection2.1,thetraditionalmethodofaveragingsquaredgradientsisdis-cussed,while,inSection2.2,anewmethodbasedonprincipalcomponentanalysis(PCA)isproposed.InSection2.3,aproofisgiventhatbothmethodsareexactlyequivalentanditisshownthatthecoherence,whichisameasureforthelocalstrengthofthedirectionalfield,canbeelegantlyexpressedinthetwoeigenvaluesthatarecomputedforthePCA.Then,inSection3,SPsarediscussed.Section3.1describesanefficientmethodfortheextractionofSPsfromtheDF,while,inSection3.2,amethodisproposedfortheestimationoftheorientationoftheSPs.InSection4,somecomputationalaspectsofDFestimationandSPextractionarediscussed.Furthermore,itisshownthatthehigh-resolutionDFcanbeusedtoobtainmoreaccurateblock-DFestimates.Finally,inSection5,anexperimentispresentedwherethetheoryisappliedtofingerprintscontainedinoneofthedatabasesusedfortheFingerprintVerificationCompetition2000[13].Inthatsection,somepracticalaspectsofthealgorithmsaredis-cussedaswell.

onthehigh-frequencypowerinthreedimensions[16],2-dimensionalspectralestimationmethods[15],andmicro-patternsthatcanbeconsideredbinarygradients[10].Theseapproachesdonotprovideasmuchaccuracyasgradient-basedmethods,mainlybecauseofthelimitednumberoffixedpossibleorientations.ThisisespeciallyimportantwhenusingtheDFfortasksliketracingflowlines.Thegradient-basedmethodwasintroducedin[17]andadoptedbymanyresearchers,see,e.g.,[18],[19],[20],[21].

Theelementaryorientationsintheimagearegivenbythegradientvector󰂉qx󰂅xYy󰂆qy󰂅xYy󰂆󰂊󰁔,whichisdefinedas:

!qx󰂅xYy󰂆

󰂈sign󰂅qx󰂆rs󰂅xYy󰂆

qy󰂅xYy󰂆

󰂅I󰂆󰀒󰀓4ds󰂅xYy󰂆5

ds󰂅xYy󰂆dxY󰂈signds󰂅xYy󰂆dxdy2DIRECTIONALFIELDESTIMATION

wheres󰂅xYy󰂆representsthegray-scaleimage.Thefirst

elementofthegradientvectorhasbeenchosentoalwaysbepositive.ThereasonforthischoiceisthatintheDF,whichisperpendiculartothegradient,oppositedirectionsindicateequivalentorientations.ItisillustratedinFig.2thatsomeaveragingoperationhastobeperformedonthegradientsinordertoobtaintheDF.

VariousmethodsusedtoestimatetheDFfromafingerprintareknownfromliterature.Theyincludematched-filterapproaches[14],[15],[9],methodsbased

2.1AveragingSquaredGradients

Thissectiondiscussestheproblemsthatareencounteredwhenaveraginggradientsandthetraditionalsolutionof

BAZENANDGEREZ:SYSTEMATICMETHODSFORTHECOMPUTATIONOFTHEDIRECTIONALFIELDSANDSINGULARPOINTSOF...907

averagingaveragingsquaredanalysissquaredgradients.gradientsFirst,ispresentedthegeneralandideathen,behindanthecoherence,estimationoftheresultsoftheofDF,thismethodisgiven.Apartfromestimatedorientation.

whichprovidesathismeasuresectionforalsothestrengthdiscussesofthethe2.1.1QualitativeAnalysis

Gradientscannotdirectlybeaveragedinsomelocalneighbor-hoodsinceoppositegradientvectorswillthencanceleachother,althoughtheyindicatethesameridge-valleyorienta-tion.Thisiscausedbythefactthatlocalridge-valleystructuresremainunchangedwhenrotatedover180degrees[21].SincethegradientorientationsaredistributedinacyclicspacerangingfromHto%,andtheaverageorientationhastobefound,anotherformulationofthisproblemisthattheª%Eperiodi󰁣In[17],a󰁣y󰁣li󰁣solutionme󰁡ntoºthishasproblemtobecomputed.

isproposedbydoublingtheanglesofthegradientvectorsbeforeaveraging.Afterdoublingtheangles,oppositegradientvectorswillpointinthesamedirectionand,therefore,willreinforceeachother,whileperpendiculargradientswillcancel.Afteraveraging,thegradientvectorshavetobeconvertedbacktotheirsingle-anglerepresentation.Theridge-valleyorientationisthenperpendicularonlyInofthetheangleversiontoofofthethethedirectiongradientsalgorithmoftheisdoubled,discussedaveragegradientvector.butinalsothispaper,thelengthnotconsideredthegradienteffectascomplexvectorsisnumberssquared,asifthegradientvectorsareaveragethatstrongorientationsthathaveareasquared.highervoteThishasinthethethisotherapproachorientation[21],choices,resultsthanweakerorientations.Furthermore,like,forininstance,thecleanestsettingexpressions.alllengthsHowever,tounityInare[17],foundamethodinliteratureisproposedaswell.

tousethesquaredgradientsforcomputationofthestrengthoftheorientation.Thismeasure,whichiscalledthecoherence,measureshowwellallsquaredgradientvectorssharethesameorientation.Iftheyareallparalleltoeachother,thecoherenceis1andiftheyareequallydistributedoveralldirections,thecoherenceis0.2.1.2QuantitativeAnalysis

Inthissection,thequalitativeanalysisthatwasgivenintheprevioussectionismadequantitative.ThegradientvectorsarefirstestimatedusingCartesiancoordinates,inwhichagradientvectorisgivenby󰂉qxqy󰂊󰁔.Fordoublingtheangleandsquaringthelength,thegradientvectorisconvertedtoºpolarºcoordinates,inwhichitisgivenby󰂉q&q9󰂊󰁔.Thisconversionisgivenby:

q!4q󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁5q&

qPx󰂇qPy9

󰂈t󰁡nÀIqX󰂅P󰂆y

NotethatÀIP%`q9 IP%isadirectconsequenceofthefacthatqxisalwayspositive.ThegradientvectorisconvertedbacktoitsCartesianrepresentationby:

q! qx

q&!

󰂈q󰁣osq9&sinq9X󰂅Q󰂆

Usingtrigonometricidentities,anexpressionforthe

squaredgradientvectors󰂉qsYxYqsYy󰂊󰁔thatdoesnotrefertoq&andq9,isfound:

qsYx

!4qP

54&󰁣osPq9qP󰂅󰁣osPq5&9ÀsinPq9󰂆qsYy󰂈󰂈4qP&sinPq9qP&󰂅Psinq9󰂈

qP5󰁣osq9󰂆

󰂅RxÀqP󰂆

PqxqyXThisresultcanalsobeobtaineddirectlybyusingtheequivalenceofªdoublingtheangleandsquaringthelengthofavectorºtoªsquaringacomplexnumberº:

qsYx󰂇jÁqsYy󰂈󰂅qx󰂇jÁqy󰂆P󰂈󰂅qPxÀqP

y󰂆󰂇jÁ󰂅Pqxqy󰂆X

󰂅S󰂆

Next,theaveragesquaredgradientÂqsYxqsYyÃ󰁔

canbecalculated.Itisaveragedinsomeneighborhood,usingapossiblynonuniformwindow󰁗:

4q5sYx 󰁐󰁗qsYx

!qsYy󰂈󰁐4󰁐󰁗qsYy

󰂈󰁐

󰁗

qP5xÀqPy !󰂅T󰂆󰂈qxxÀqyyX󰁗PqxqyPqxyInthisexpression,

q󰁘

xx󰂈qP󰂅U󰂆

󰁗

xq󰁘

yy󰂈qPy󰂅V󰂆

󰁗

q󰁘

xy󰂈

qxqy

󰂅W󰂆

󰁗

areestimatesforthevariancesandcrosscovarianceofqx

andqy,averagedoverthewindow󰁗.Now,theaverage

gradientdirectionÈ,withÀIP%`È IP%,isgivenby:

È󰂈IÀ

ÁP󰂀qxxÀqyyYPqxyY

󰂅IH󰂆

where󰂀󰂅xYy󰂆V

isdefinedas:

󰂆󰂈`t󰁡nÀI󰂀󰂅xYy󰂅yax󰂆

t󰁡nÀIt󰁡nÀI󰂅󰂅yaxyax󰂆󰂇%

forx󰂆À%

x!H

x``HH󰁞󰁞yy!`H

󰂅II󰂆

andtheaverageridge-valleydirection󰀒,withÀIItoÈ:

P%`󰀒 P%,isperpendicular&

󰀒󰂈ÈÈ󰂇IÀPI%forÈ HP%

ÈbHX󰂅IP󰂆Thecoherenceofthesquaredgradientscanalsobe

expressedusingthesamenotations.Thecoherencegohisgivenby[17]:

󰀌goh󰂈󰀌󰁐󰁐󰁗󰀌󰀌󰂅qsYxYq󰀌sYy󰂆󰀌󰂅q󰀌sYxYqsYy󰂆󰀌X󰂅IQ󰂆󰁗

908IEEETRANSACTIONSONPATTERNANALYSISANDMACHINEINTELLIGENCE,VOL.24,NO.7,JULY2002

sameIfallthedirection,squaredthegradientsumofvectorsthemoduliarepointinginexactlythecoherencemodulusgradientvalueofthesumofthevectors,oftheresultingvectorsequalsinalengthvectorsareofequally1.Onthedistributedotherhand,inallifdirections,thesquaredcoherenceofthesituations,valuesumofofthevectorswillequal0,resultingintheaprovidingthetherequiredcoherence0.Inmeasure.

willbetweenvarybetweenthese0twoandextreme1,thus2.2PrincipalComponentAnalysis

Thisdirectionalpaperproposesasecondmethodtoestimatetheprincipalfieldfromthegradients,whichisbasedonorthogonalcomponentanalysis(PCA).PCAcomputesanewthebasevariancebaseofthegivenprojectionamultidimensionalononeofthedateaxessetsuchthatminimal.ismaximal,eigenvectorsItofturnswhiletheprojectionontheotherofthisonenewistheautocovarianceoutthatthematrixbaseisofthisformeddatasetbythe󰂉GaussianqWhenapplyingPCAtotheautocovariancematrixof[22].thexqy󰂊󰁔Fromcalculated.

thisjointgradientvectors,itprovidesthe2-dimensionalfunction,probabilitythemaindensitydirectionfunctionoftheofgradientsthesevectors.canbegradientTheestimatevectorpairsoftheisgivenautocovarianceby:

matrixgofthe !g󰂈

q󰁘 qxxqxyqPqxq!

xyqyy󰂈󰁗

qPyxqyy

X󰂅IR󰂆Invectorsthisestimate,arezero-mean,theassumptioni.e.,

ismadethatthegradienti󰂉qx󰂊󰂈i󰂉qy󰂊󰂈H

󰂅IS󰂆

inwindowawindow󰁗inthegivenfingerprint.Thisistrueinanyvalue.valuesThen,inwhichthegradientthefingerprintisdefinedhasasatheconstantmeangrayexpectationthatconstantofhavethethegradientsamedifferenceoftwoisexpectation.zero.Therefore,thesmallnumbermeanofisridge-valleyreasonabletransitions.

inwindowsTherequirementthatcontainofadensityThelongestautocovariancefunctionaxisvisIofgiventhe2-dimensionalbytheeigenvectorjointprobability!variance.ThisaxiscorrespondsmatrixthatbelongstotothelargesteigenvalueoftheIgradientofperpendicularorientation.thegradientsislargest,thedirectionandsotointhewhichªaverageºtheshortestbelongsaxisvalleyorientationtothevto.thisTheaxisridge-valleyand,therefore,orientationsgivenbyarethePsmallestThisisthe󰀒isgiveneigenvaluedirectionby:

!oftheTheeigenvectoraverageridge-thatP.󰀒󰂈󰂀vPX

󰂅IT󰂆

simpleTheªstrengthºstrengthfunctionbetweenof󰁓tr0theofandtwothe1,eigenvalues.orientationcanbedefinedasaitisdefinedInby:

ordertolimitthe󰁓tr󰂈

!IÀ!P

!I󰂇!P

󰂅IU󰂆

Again,!ifallgradientsover󰂈Hallandangles,󰁓tr󰂈!I,while,areinpointingcaseofinauniformthesamedistributiondirection,PI󰂈!Pand󰁓tr󰂈H.

2.3Comparison

Inmethodsthissection,methodsofDFaestimation.comparisonAismadebetweenthetwocoherencearesectiongohexactlyandequivalentproofanditisisgivenshownthatthatboththemathematicalprovidesstrength󰁓trareequivalentaswell.Thisdetailsabriefdescriptionoftheproofs;thecalculatedTheproofcanbefoundinAppendixAandB.asdescribedbystartsbyderivingtheaveragegradient,intheSectionmethod2.1.ofInAppendixaveragingA,squareditisshowngradientsthat:

I4Iqx󰂈ÁP󰂅qq󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁5xxÀqyy󰂆󰂇IP󰂅qxxÀqyy󰂆P󰂇RqPxyy󰁣qxy

󰂅IV󰂆with

r󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰁣󰂈IP󰂅qxxÀqyy󰂆󰂇Iq󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁P󰂅qxxÀqyy󰂆P󰂇RqPxyX󰂅IW󰂆

autocovarianceNext,itisshownthatthisvectoristhatbothmethodsmatrixareequivalent.

g,asdefinedin(14),aneigenvectorwhichprovesof

gradientThecoherenceareexactlymethodequalas(seegohwell.(13)),calculatedInandAppendixthestrengthusingB,itis󰁓trtheshown(seesquaredthat

(17))q󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰁓tr󰂈goh󰂈

󰂅qÀq󰂁xxyy󰂆P󰂇RqPxy

qxx󰂇qyy

X󰂅PH󰂆3SINGULARPOINTEXTRACTION

ThethesubjectofthissectionisFig.pointsinafingerprintwhereextractiontheDFofisthediscontinuous.SPs,whichareInone3,arecontainingtwosegmentsacoreofandtheonefingerprintofFig.1areshown,cannotsomewhereonebelocatedinthecenterofthecontainingsegments.aHowever,delta.ThetheySPswhichridge-valleymoreaccuratelythanwithinthewidthofisapproximatelystructure10inthegray-valuefingerprint,theInFig.4,theDFofthosesegmentspixelsforisthisshown.example.

FromthisDF,accuracyexactstraightforwardofSPonlylocationonepixel.canbeAlthoughdetermineditseemseasilylikewithandifferentliterature.

algorithmstasktoforextractSPextractiontheSPsfromaveryaretheknownDFs,manyfromareas.In[23],differenceThen,firstaareasfeatureofhighcurvatureareidentifiedassearchofaroundadoublebetweencoretheestimatedvectorisdirectionestimatedandbythetakingdirectionthebeingacandidate(whorl)area.inThisanumberfeatureofvectorpositionsisclassifiedinacirclecandidatecore,featureareasdelta,ofhighwhorl,curvatureornoneareofthese.In[24],firstasatisfourpositionsvectorisconstructedaroundthebytakingtheselected,averagetoo.directionsThen,aareclassifiedasacoreordelta.candidateIn[18],someSP.Thisreferencefeaturemodelsvectorsquaresshiftedmeasurefit.over[14],forInhow[21],themuchtheDF,thelocalandlocalenergySPsaredetectedbyaleast-DFresemblesoftheDFanisSPusedand,asaFinally,aneuralregionsinisused[25],networktheasaratioisslidedovertheDFtodetectSPs.inmeasureofthetosinesdetectoftheSPs.

DFsintwoadjacentBAZENANDGEREZ:SYSTEMATICMETHODSFORTHECOMPUTATIONOFTHEDIRECTIONALFIELDSANDSINGULARPOINTSOF...909

Fig.3.Segmentsofafingerprintthatcontainasingularpoint.(a)Coreand(b)delta.

Fig.4.Directionalfields.(a)Coreand(b)delta.

Thesemethodsallprovidesomewhatunsatisfactoryresultssincetheyarenotcapableofconsistentlyextractingthesingularpoints.InsteadofprovidingaBooleanoutputthatindicateswhetheranSPispresentatsomelocationornot,theyproduceacontinuousoutputthatindicateshowmuchthelocalDFresemblesaSP.Postprocessingsteps,likethresholdsandheuristics,arenecessarytointerprettheoutputsofthealgorithmsandtomakethefinaldecisions.Themethodthatispresentedinthissectionisbasedon

Âindex,whichwasfirstintroducedin[10].ThethePoincare

ÂindexcanbeexplainedusingtheDFsthatarePoincare

depictedinFig.4.FollowingacounterclockwiseclosedcontouraroundacoreintheDFandaddingthedifferencesbetweenthesubsequentanglesresultsinacumulativechangeintheorientationof%andcarryingoutthisprocedurearoundadeltaresultsinÀ%.However,whenappliedtolocationsthatdonotcontainanSP,thecumulativeorientationchangewillbezero.

ÂindexprovidesthemeansforAlthoughthePoincare

consistentdetectionofSPs,thequestionariseshowtocalculatethismeasure.Apartfromtheproblemofhowtocalculatecumulativeorientationchangesovercontoursefficiently,achoicehastobemadeontheoptimalsizeandshapeofthecontour.Apossibleimplementationisdescribedin[26].Thatpaperclaimsthatasquarecurvewithalengthof25pixelsisoptimal.Asmallercurveresultsinspuriousdetections,whilealargercurvemayignore

core-deltapairswhichareclosetoeachother.Ifthepostprocessingstepfindsaconnectedareaofmorethan

Âindexis!%,acoreorsevenpixelsinwhichthePoincare

deltaisdetected.Inthecaseofanareathatislargerthan20connectedpixels,twocoresaredetected.

InSection3.1,weproposeanefficientimplementationofan

ÂindexSPextractionalgorithmthatisbasedonthePoincare

andmakesuseofsmall2-dimensionalfilters.ThealgorithmextractsallsingularpointsfromtheDF,includingfalseSPsthatarecausedbyaninsufficientlyaveragedDF.Further-more,thealgorithmdetermineswhetheracoreoradeltaisdetected.

Section3.2presentsanalgorithmforestimatingtheorientationofSPs.Asfarasweknow,thereexistsonlyoneearlierpublicationoncomputingtheorientationofSPs[23].ThatmethodexaminestheDFatanumberoffixedpositionsinacirclearoundtheSPandtakesthepositionwheretheDFpointsbesttowardtheSPasorientationoftheSP.ThemethodthatisdescribedbelowusestheentireneighborhoodoftheSPfortheorientationestimate,thusprovidingmuchmoreaccurateresults.

3.1ExtractionofSingularPoints

Intheimplementationthatisproposedinthispaper,choicesofthesizeandshapeofthecontourdon'thavetobemade.Postprocessingstepsarenotnecessaryandthecumulativeorientationchangesovercontoursareimplemented

910IEEETRANSACTIONSONPATTERNANALYSISANDMACHINEINTELLIGENCE,VOL.24,NO.7,JULY2002

Fig.5.Squareddirectionalfields.(a)Coreand(b)delta.

Fig.6.Gradientofsquareddirectionalfields.(a)Coreand(b)delta.

efficientlyinsmall2-dimensionalfilters.ThemethodcomputesforeachindividualpixelwhetheritisanSP,andisthereforecapableofdetectingSPsthatarelocatedonlyafewpixelsapart.ThispropertyisespeciallyusefulfortheextractionofSPsfromblock-directionalfields(BDFs),whichestimateonedirectionforeachnÂnblock.Specialcarehastobetakenthathigh-resolutionDFsaresufficientlyaveragedsuchthatspuriousSPsareeliminatedbeforehand,astheSP-extractionalgorithmwilldetectallSPspresentintheDFofagivenresolution.

Thealgorithmfirsttakesthesquareddirectionalfield(SDF).Thiseliminatesthestepof%whichisencounteredin

ItheDFbetweentheorientations󰀒󰂈IP%and󰀒󰂈ÀP%.The

ÂindexeschangetoP%,ÀP%,and0for,respectively,aPoincare

core,adelta,andnoneofthese.TheorientationoftheSDF,denotedbyP󰀒,isdepictedinFig.5fortheareasaroundSPs.Summingthechangesinorientationcorrespondstosummingthegradientsofthesquaredorientation.Thegradientvectortcanbeefficientlyprecalculatedfortheentireimageby:

45 !dP󰀒󰂅xYy󰂆

tx󰂅xYy󰂆dx󰂈rP󰀒󰂅xYy󰂆󰂈dP󰀒󰂅PI󰂆󰂅xYy󰂆Xty󰂅xYy󰂆

dygradientvectorsofthesquaredorientationaroundboth

singularpointsareshowninFig.6.

ThenextstepistheapplicationofGreen'sTheorem,whichstatesthataclosedline-integraloveravectorfieldcanbecalculatedasthesurfaceintegralovertherotationofthisvectorfield:

s󰁚󰁚

wxdx󰂇wydy󰂈rot󰂉wxwy󰂊󰁔dxdyde

󰀓󰁚󰁚e󰀒󰂅PP󰂆

dwydwx

ÀdxdyY󰂈

dxdyewherexandydefinethecoordinatesystem,eisthearea,

anddeisthecontouraroundthisareaand󰂉wxwy󰂊󰁔isthevectorfield.Thistheoremisappliedtothesummationofthegradientsofthesquaredorientationoverthecontour:

󰁘󰁘

󰂅txÁÁx󰂇tyÁÁy󰂆󰂈rot󰂉txty󰂊󰁔sndex󰂈

ÁxYÁy󰁡longde

󰂈

󰁘󰀒

dtydtxÀXdxdy󰂅PQ󰂆

󰀓

Inthecalculationofthediscreteversionofthisgradient,

bothcomponentsoftshouldbecalculatedªmoduloP%,ºsuchthattheyarealwaysbetweenÀ%and%.ThismakesthetransitionfromP󰀒󰂈À%toP󰀒󰂈%continuousor,inotherwords,theorientationisconsideredtobecyclic.The

SinceallSPshavetobeextractedfromtheDF,eistakenasasquareofonepixel.Thisresultsinaveryefficient

Âindex.ApplicationmethodforcomputationofthePoincare

oftheproposedmethodwillindeedleadtothedesiredSPlocations.UnlikeallotherSPextractionmethods,acore

ÂindexofP%,adeltainÀP%whiletheresultsinaPoincare

BAZENANDGEREZ:SYSTEMATICMETHODSFORTHECOMPUTATIONOFTHEDIRECTIONALFIELDSANDSINGULARPOINTSOF...911

Fig.7.Rotationofthegradientofthesquareddirectionalfields.(a)Coreand(b)delta.

Fig.8.Referencemodelsofsingularpoints.(a)Coreand(b)delta.

indexforallotherpixelsintheimageisexactlyequalto0.ThisisillustratedinFig.7.

TheexactlocationsoftheSPsintheDFarejustbetweenthepixels.OurmethoddetectsanSPinallneighboringpixelsofthepoint,becauseoftheregionofsupportofthegradientoperator.ThisresultsinSPdetectionsthathaveasizeofPÂPpixels,ascanalsobeseeninFig.7.

usefulnessofthesquaredgradientsiscausedbythefactthat,whenthegray-scaleimagerotatesaroundthecore,allcomponentsoftheSDFrotateoverthesameangle,asshowninAppendixC.Therefore,themodelofacorethathasrotatedoveranangle9,isgivenbyareferencemodelwithallitscomponentsmultipliedbyej9.

󰁓hp󰁣oreY9󰂈󰁓hp󰁣oreYrefÁej9X

󰂅PT󰂆

3.2OrientationofSingularPoints

Thelastsubjectofthispaperistheestimationoftheorientations9oftheextractedSPs.Themethodthatisdescribedhere,makesuseofthesquaredgradientvectorsintheneighborhoodofanSP,bothfortheimagetobeanalyzedandforareferenceSP.First,referencemodelsoftheDFsaroundstandardcoresanddeltasareconstructed.Foracoreat󰂅xYy󰂆󰂈󰂅HYH󰂆,thereferencemodelthatdescribestheSDFisgivenby:

󰂅yYÀx󰂆

󰁓hp󰁣oreYref󰂈p󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁xP󰂇yP

and,foradeltaat󰂅xYy󰂆󰂈󰂅HYH󰂆,itisgivenby:

󰂅ÀyYÀx󰂆

󰁓hpdelt󰁡Yref󰂈p󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁X

xP󰂇yP

󰂅PS󰂆󰂅PR󰂆

Thispropertyisusedfortheestimationoftheorientationofthecore.Theorientationofthecorewithrespecttothereferencemodelisfoundbytakingtheelement-by-elementproductoftheobservedsquaredgradientdata󰁓hp󰁣oreYo󰁢s󰂅xYy󰂆andthecomplexconjugatedofthereferencemodel󰁓hp󰁣oreYref󰂅xYy󰂆.ThisisdepictedinFig.9c.Then,theelementsaresummedandthesumisdividedbythenumberofmatrixelementsx,andtheangleoftheresultingvectoristaken.

󰁞g󰂈󰂀9

I󰁘Ã

󰁓hp󰁣oreYref󰂅xYy󰂆Á󰁓hp󰁣oreYo󰁢s󰂅xYy󰂆XxxYy

󰂅PU󰂆

Notethatj󰁓hp󰁣oreYrefj󰂈j󰁓hpdelt󰁡Yrefj󰂈Iforall󰂅xYy󰂆.TheDFs

thatareassociatedwiththesemodelsareshowninFig.8.TheSDFintheneighborhoodofacore,repeatedinFig.9a,ideallylookslikethereferencemodelinFig.9b.The

Therelativeorientationofadeltawithrespecttothereferencemodelisgivenbyonethirdoftheangleoftheelement-by-elementproduct,asalsoshowninAppendixC:

II󰁘Ã

󰁞h󰂈󰂀󰁓hpdelt󰁡9Yref󰂅xYy󰂆Á󰁓hpdelt󰁡Yo󰁢s󰂅xYy󰂆XQxxYy

󰂅PV󰂆

912IEEETRANSACTIONSONPATTERNANALYSISANDMACHINEINTELLIGENCE,VOL.24,NO.7,JULY2002

Fig.9.Processingstepsinthecalculationoftheorientationofacore.(a)SDFaroundcore.(b)SDFaroundreferencecore.(c)Orientationestimate.

Theaveragingoperatorprovidesanaccurateandunbiasedestimatefortheorientations9gand9h.Iftheobservedcoreisexactlyarotatedversionofthereferencecore,theorientationestimategives:󰁞g󰂈󰂀9

I󰁘Ãj9

󰁓hp󰁣oreYref󰂅xYy󰂆Á󰁓hp󰁣oreYref󰂅xYy󰂆ÁexxYy

󰀌I󰁘󰀌󰀌󰁓hp󰁣oreYref󰂅xYy󰂆󰀌PÁej9󰂈󰂀

xxYy󰂈󰂀ej9󰂈9X

WhenapplyingtheorientationestimatetothecoreofFig.3,itisfoundtoberotated4degreesclockwisewithrespecttothereferencecoreofFig.8,whilethedeltaofFig.3isfoundtoberotated8degreescounterclockwisewithrespecttothereferencedeltaofFig.8.Thiscorrespondstotheestimatesthatweremadebyvisualinspection.

󰂅PW󰂆

estimatedbymeansofdecimationofthehigh-resolutionDF.Scale-spacetheorytellsthataveragingwithaGaussianwindow󰁗minimizestheamountofartifactsthatareintroducedbysubsampling[4].ThiswillreducethenumberoffalsesingularpointsintheDFconsiderably.

Frommultiratesignalprocessing,itisknownthatthefilteringanddecimationstepscanbeimplementedveryefficientlyusingpolyphasefiltersbyinterchangingtheorderofdecimationandfiltering[27].Usingthismethod,thecalculationofaRÂRBDFisexpectedtotake40msona500MHzPentiumIII,whilethecalculationofanVÂVBDFisexpectedtotakeonly20ms.SincetheSPextractionalgorithmmakesuseofsmall2-dimensionalfilters,ittakes150msforaQHHÂQHHDF.Itisexpectedtotakeonly10mstoextracttheSPsfromaRÂRBDFofafingerprintofQHHÂQHHpixels.

5EXPERIMENTALRESULTS

4COMPUTATIONALASPECTS

ForefficientcalculationoftheDFandthecoherence,oneshouldnotuseeitherofthetwobasicmethods.Instead,first(7),(8),and(9)areusedforestimationofqxx,qyy,andqxy,andsubsequently(51)and(58)areusedforcalculationoftheDFandthecoherence.Whencalculatingthoseforallpixelsintheimage,thesummationsover󰁗reducetolinearfilteroperations,whichcanbeimplementedveryeffi-ciently.Ona500MHzPentiumIIIcomputer,anefficientC++implementationforcalculationoftheDFandthecoherencetakesapproximately300msofprocessingtimeforafingerprintof300by300pixels.

FormostDF-relatedtasks,suchahighresolutionestimateisnotneeded.Inthesecases,asimpleblock-directionalfield(BDF)withblocksof,forinstance,VÂVpixelsprovidesenoughaccuracy.TheclassicalwaytoestimateaBDFistopartitiontheimageintoblocksandestimateqxx,qyy,andqxyastheaverageoftheblock.Sometimes,overlappingblocksareusedforsomemorenoisesuppression.However,averagingwithauniformwindow󰁗doesnotsuppressthehigh-frequencynoisesufficiently.Therefore,aliasingintroducesartifactsintheDF,which,inturn,createsfalsesingularpoints.Thecauseofthisproblemisthatthelengthoftheaveragingfilterissettothesamenumberasthedecimationrate.Thiscanbesolvedbydecouplingthesizeandtheshapeoftheaveragingfilter󰁗fromthesubsamplingrate.WeproposetheuseofanalternativeBDFcalculationmethodthatisbasedonthehigh-resolutionDF.Ineachblock,qxx,qyy,andqxyare

Inthissection,someexperimentswillbepresentedinwhichthepreviouslyderivedresultsareappliedtoalargenumberoffingerprints.ItwillbeshownthatapplicationofthesemethodsenablestheestimationofveryaccurateandhighresolutionDFs,accurateSPlocations,andcorrectorienta-tionsofthesingularpoints.

WehaverunourexperimentsontheseconddatabaseoftheFVC2000contest[13].Thisdatabasecontainsfingerprintimagesthatarecapturedbyacapacitivesensorwitharesolutionof500pixelsperinch.Thismeansthattwoadjacentridgesarelocatedeightto12pixelsapart.Inthisdatabase,110untrainedindividualsareenrolled,eachwitheightprintsofthesamefinger.

SincethereexistsnogroundtruthfortheDFoffingerprints,objectiveerrormeasurescannotbeconstructed.Therefore,itisdifficulttoevaluatethequalityofaDFestimatequantitatively.Alternatively,thequalityofaDFestimatehastobemeasuredindirectly.Thissectionisorganizedasfollows:First,inSection5.1,thequalityoftheDFisassessedbymeansofmanualinspection.Next,inSection5.2,thenumberoffalseSPsisusedasameasureforthequalityofaDFestimate.However,thismeasurealsodependsonthesegmentationmeasureused.Then,Section5.3presentsexperimentalresultsontheorientationestimationoftheSPs.

5.1DirectionalFieldEstimation

Mostauthorsprocessfingerprintsblockwise[9],[20].Thismeansthatthedirectionalfieldisnotcalculatedforallpixelsindividually.Instead,theaverageDFiscalculatedinblocksof,forinstance,16by16pixels.Inthissection,itwill

BAZENANDGEREZ:SYSTEMATICMETHODSFORTHECOMPUTATIONOFTHEDIRECTIONALFIELDSANDSINGULARPOINTSOF...913

Fig.10.Gray-scalecodeddirectionalfieldandcoherence.(a)Directionalfieldand(b)coherence.

Fig.11.Gradientsanddirectionalfieldforvariousvaluesof'.

beshownthattheprocessingcanbecarriedoutpixelwise,leadingtoahighresolutionandaccurateDFestimate.

ThefirstexperimentconsidersthefingerprintofFig.1.AlthoughtheDFisonlyshownatdiscretestepsinFig.1b,itisestimatedforeachpixel.Thisisillustratedinthegray-scalecodedFig.10a.Inthatfigure,theanglesintherangeof

IÀIP%toP%haveuniformlybeenmappedtothegray-levelsfromblacktowhite.Thefigureissomewhatchaoticattheborderssincethoseareareasthatconsistofnoise.However,asshowninFig.10b,thecoherenceisverylowinthesenoisyareas[5].Inthisfigure,blackindicatesgoh󰂈H,whilewhiteindicatesmaximumcoherence.

Next,anexperimentiscarriedouttoillustratetheeffectsofthechoiceofthewindow󰁗.WehavechosenaGaussianwindow,inaccordancewiththescale-spacetheory[4].InFig.11,theDFinasmallsegmentofPSÂPHpixelsisshown.Thissegmentcontainsabrokenridgethatisalmosthorizontal.Inthisexperiment,'ischosenintherangefrom'󰂈Ito'󰂈S.ItcanbeseenthattheDFisveryerraticforsmallvaluesof'.For

highervaluesof',theDFbecomesmoreuniform,andthelinesgetlonger,indicatinghighercoherencevalues.

Fromthisexperiment,awindowwith'󰂈Sseemsagoodchoice.Forthisvalue,theDFaroundabrokenridgeissufficientlyaveraged.Thewindowhasthenaneffectiveregionofsupportofapproximately20pixels(P'oneachside),whichcorrespondstoapproximatelytworidge-valleystructures.

5.2SingularPointExtraction

InSection3,ithasbeenshownthattheSPextractionmethodcorrectlyextractsSPsfromthesmoothDFofFig.4.ThiswasalsoillustratedinFig.1cforthefingerprintofFig.1a.Inthissection,thequestionwillbeansweredabouthowwellthemethodperformsonalargersetofDFsthatareestimatedfromrealfingerprints.

AsalreadymentionedinSection3,ourmethodextractsallSPsfromtheDF.Incasethedirectionalfieldisnotaveragedsufficiently,thismayresultinmanyfalsesingularpoints.ADFthathasnotbeenaveragedatall,maycontain

914IEEETRANSACTIONSONPATTERNANALYSISANDMACHINEINTELLIGENCE,VOL.24,NO.7,JULY2002

Fig.12.Extractedsingularpointsforvariousvaluesof'.

asmanyas100spuriouscore-deltapairs,especiallyinnoisyregionslikethebordersoftheimage.WhenaveragingtheDF,thesepairseithermergeanddisappearorfloatofftheborderoftheimage[21].ThisisillustratedinFig.12,wheretheextractedSPsareshownforvariousvaluesof'.AnotherexampleofthisbehaviorcanbeseenfromFig.11.For'󰂈I,asmanyasfivefalsecoresandfivefalsedeltascanbeidentified,whichalldisappearfor'!Q.

Infingerprintrecognition,onlytheSPsattheridge-valleyscalearevalidSPs.ThismeansthattheSPshavetobeextractedfromaDFthatisestimatedatthisscale[4].Thecoarse-scaledirectionalfieldcanbeobtainedbyaveragingitusingthealgorithmsofSection2.Next,theproposedSPextractionmethodcanbeapplied.Infact,scaleandsingularpointextractionaretwodifferentproblems.TheSPextractionmethodwillonlyprovidesatisfactoryresultsifthescaleischosenwellbysufficientaveraging.Sinceafingerprintnevercontainsmorethantwocore-deltapairs,thismightprovideachecktoseewhethertherightscalehasbeenreached.Experimentshaveshownthat'󰂈Tisoptimalforthedatabasethatisusedinthissection.

EvenwhentheDFhasbeenaveragedsufficiently,thenoisyregionsoutsidethefingerprintareamaystillcontainsomesingularpoints,ascanalsobeseenfromFigs.10aand12.Moreaveragingintheseregionsoflowcoherencedoesnotalwayssolvethisproblem:Somefalsesingularpointswillremain.Thismayalsobethecaseinfingerprintregionsthatareverynoisy.

AsolutionistousesegmentationinordertodiscardthefalseSPs.Segmentationisthepartitioningoftheimageina

ªforegroundºfingerprintareaandaªbackgroundºnoisearea.Aftersegmentation,allSPsthatareinthebackgroundcanbediscarded.Segmentationofinkedfingerprintimagesisarelativelystraightforwardtasksincethebackgroundcontainsnotmuchnoise.Therefore,measureslikethelocalmeangraylevelandthelocalvarianceofthegraylevelcanbeused[19].However,thesegmentationoflive-scannedfingerprintimagesismuchharder,sincetheycontainmuchmorebackgroundnoise.Therefore,moreadvancedsegmen-tationmethodsthatuse,forinstance,thecoherenceasmeasurehavetobeused.

Inourexperiment,SPsareextractedfromthefirstprintsofallfingersofthesecondFVC2000database,usingthemethodofSection3andaGaussianwindowwith'󰂈T.Forthepurposeofreference,theSPsinallprintsweremarkedbyhumaninspection.TheaveragenumberoffalseandmissedSPsareshowninTable1,whilethedistributionof

TABLE1

ResultsofSPExtraction

BAZENANDGEREZ:SYSTEMATICMETHODSFORTHECOMPUTATIONOFTHEDIRECTIONALFIELDSANDSINGULARPOINTSOF...915

Fig.13.Distributionofthenumberoffalsesingularpointsforvarioussegmentationmethods.(a)Nosegmentation.(b)Manualsegmentation.(c)Segmentation1.(d)Segmentation2.

Fig.14.SPextractionforexamplesfromeachofthefiveHenryclasses.(a)Whorl.(b)Leftloop.(c)Rightloop.(d)Arch.(e)Tentedarch.

Fig.15.ExampleofextractionofspuriousSPs.(a)Fingerprint.(b)CenterArea.(c)DFofcenterarea.

thenumbersoffalseSPsisshowninFig.13forfourdifferenttypesofsegmentation:

Nosegmentation,thewholeimageistakenasfingerprintregion.2.Manualsegmentation.

3.Highresolutionsegmentationalgorithmthatuses

thecoherenceestimateasfeatureandmorphologicaloperatorstosmooththesegmentationresult[5].4.Highresolutionsegmentationalgorithmthatuses

thecoherence,themean,andthevarianceofthefingerprintimageasfeaturesandmorphologicaloperatorstosmooththesegmentationresult[6].InFig.14,theextractedSPsforfingerprintsofthefiveHenryclassesareshown.ItcanbeseenthattheSP-extractionalgorithmhasnodifficultiesindistinguishing1.atentedarch,whichcontainsonecoreandonedelta,fromanarch,whichcontainsneitherofboth.Furthermore,thefigureshowsthatthedeltaintherightloopisnotdetected,althoughitisvisibleintheimage.Thesegmentationboundary,whichisalsoshowninthefigure,positionsthisdeltajustoutsidetheforegroundarea.

InFig.15,anexampleoftheextractionofspuriousSPsisshown.Fromthesurroundingsofthenoisycenterarea,itcanbeconcludedthatthisareashouldcontainonecore.However,theDFcontainstwocoresandonedeltainthisarea.FromtheshortlinesintheDFofFig.15c,itcanbeseenthatthecoherenceisverylowinthisarea.ThesefalseSPscanbeeliminatedbyfurtheraveragingtheDF,butthattakesawindowaslargeas'󰂈II.Inthiscase,itwouldbeabettersolutiontodevelopsegmentationalgorithmsthatarecapableofdetectinglow-qualityareasanddiscardspurious

916IEEETRANSACTIONSONPATTERNANALYSISANDMACHINEINTELLIGENCE,VOL.24,NO.7,JULY2002

core-deltaofentireveryprint,badpairsshouldquality,fromthesebehavingareas.rejectedalowFurthermore,fingerprintsentirely.

coherencevalueinthe5.3OrientationofSingularPoints

Theorientationlastexperimentexperiment,ofmarkedfirstSPsusingshowstheaccuracyoftheestimatedtheorientationsthemethodofofSectionallvalid3.2.SPsInthisautomatically.

manually.Next,theseorientationsaredeterminedareeThethe9󰂈9

󰁞Àdistribution9,isasfollows:oftheTheerrorsestimateofistheunbiasedorientations,sinceFurthermore,meanerrorwhichthevarianceisme󰁡n󰂉ofe9󰂊the󰂈ÀHXHIP󰂈ÀHXUdegrees.HprovidesXPI󰂈IPmeansandegrees.thatthestandarddeviationestimateisis'Ponlye9󰂈H'XHRR,e9󰂈accurateTherefore,estimateweofconcludetheorientationsthatourofmethodSPs.

6CONCLUSIONS

Indirectionalthispaper,provenfieldsanewPCA-basedmethodforestimating

asthatthismethodfromfingerprintsprovidesexactlyisproposed.theSinceitisviewtheestimatingandtraditionalanincreasemethod,themethodofferssameadifferentresultstheanªaverageºofgradient.insightItonispointedtheproblemoutofeithermethodsaccuracytoestimatethatareahigh-resolutionpresentedinthisDFpaperortoimprovecanbeusedthatthethisTheimplementedpapersingular-point-extractionofblockdirectionalfields.

offersconsistentbinarymethoddecisionsthatisproposedandcanbeintionpostprocessing.SPextractionveryefficiently.anddoesItiscapableofhighresolu-resolutiontheDFFurthermore,notitisneedshowntousethatheuristicahigh-SPorientationcanofSPs.beTousedfurtherfortheaccurateestimationofdevelopedextraction,improvetheerrorratesofathataccuratesegmentationalgorithmshavetobediscardedfingerprint.arefromThen,capabletheseareas.

spuriousofdetectingcore-deltalow-qualitypairsareascanbeinACKNOWLEDGMENTS

ThisComputationalresearchhasbeencarriedoutwithinthetherhein-Westfalen,EuropeanCommission,IntelligenceCenterinthescopeTheoftheNetherlands,(ECIC),subsidizedEuregioInterregProgram.

andNord-byAPPENDIXAEQUIVALENCE

DFESTIMATIONMETHODS

ItPCA-basedwillbeproventhatthesquaredgradientmethodandequivalent.methodwhichwasgivenTheprooffortobe:

startstheestimationbyderivingofthetheDFinverseareexactlythe

of(4), qqsYx! sYy󰂈qPPqqP!xÀyxqyX󰂅QH󰂆givenSubstitutingby

thelowerpartofthisexpression,whichis

qy󰂈

qsYyPqx

󰂅QI󰂆

intotheupperpart,givenby

qsYx󰂈󰂅qPxÀqP

y󰂆

󰂅QP󰂆

gives

qRxÀqsYxqP

ÀIRqsYy󰂈HX󰂅QQ󰂆

Solvingthisforqxgives:

Vbbr󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁bbbIbbPq󰂇Pq󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁q󰂁󰂁sYxPsYx󰂇qPsYybPbbbr󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁q`ÀI󰂇Pq󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁PPqsYxqPsYx󰂇qP󰂁󰂁sYy

x󰂈bbr󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁bI󰂅QR󰂆

bbbbPqq󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁sYxÀPqPbPsYx󰂇qP󰂁bbbr󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁sYyXÀIq󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁PPqsYxÀPqPsYx󰂇qPsYy

qThealwayssecondpositive.andfourthFurthermore,solutionscansince

beeliminatedsincexisq󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁qPsYx󰂇qP󰂁

sYy!qsYxYthenumber.thirdTherefore,solutionresultsonlytheinfirstthesquaresolutionrootisvalid:

ofanegative

r󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁qq󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁x󰂈IPPqsYx󰂇PqPsYx󰂇qPsYyX󰂅QS󰂆overThenextstepistoconsiderthesquaredgradients,averagedthewindow󰁗andtosubstitute,accordingto(6):

qsYx󰂈qxxÀqyy󰂅QT󰂆qsYy󰂈PqxyX

󰂅QU󰂆

squaredTheaveragegradients,gradients,are:

derivedfromtheaveragedqx󰂈

Ir󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁q󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁Pr󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁PqsYx󰂇PqsYxP󰂇qsYyP

󰂈Iq󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂅QV󰂆P󰂅qxxÀqyy󰂆󰂇IP󰂅qxxÀqyy󰂆P󰂇RqPxyand

qy󰂈

qsYyqxyPqx󰂈qx

󰂈r󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁qIIqxy

󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁X

󰂅QW󰂆

P󰂅qxx

Àqyy󰂆󰂇P󰂅qxxÀqyy󰂆P󰂇RqPxy

Now,itwillbeshownthatthevector:

q!4q󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁P󰂁5qxII󰁣P󰂅qxxÀqyy󰂆󰂇IqP󰂅qxxÀqyy󰂆󰂇RqPxyy󰂈Á

󰂅RH󰂆

with:

r󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰁣󰂈IP󰂅qxxÀqyy󰂆󰂇Iq󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁P󰂅qRqP󰂁

xxÀqyy󰂆P󰂇xy󰂅RI󰂆

isdefinedaneigenvectorin(14).Thisofautocovariancewillprovethatmatrixbothmethodsg,whichare

BAZENANDGEREZ:SYSTEMATICMETHODSFORTHECOMPUTATIONOFTHEDIRECTIONALFIELDSANDSINGULARPOINTSOF...917

equivalent.expressionmustForhold:

theeigenvectorsofg,thefollowinggÁ󰁖󰂈󰁖ÁÃY

󰂅RP󰂆

wherethethecolumnsof󰁖aretheeigenvectorsofgandÃexpressiondiagonalcorrespondingmustmatrixeigenvaluealsooftheholdcorresponding!foroneeigenvectoreigenvalues.isvThisIwithI:

gÁvI󰂈!IÁvI

󰂅RQ󰂆

Inordertoshowthis,󰂉qxqy󰂊󰁔issubstitutedforvI

!vI󰂈qqx

y󰂅RR󰂆

intheleft-handsideof(43).Thisgives:g ÁvI󰂈qxxqxy!ÁI

Á4

qxyqyy

󰁣IP󰂅qxxÀqyy󰂆󰂇Iq󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁P󰂅q󰂆P󰂇RqP󰂁5xxÀqyyxy󰂈I

Pqxy

󰀐

TIIq󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰁣ÁPP󰂁󰀑PQRq

xxP󰂅qxxÀqyy󰂆󰂇Pq󰀐

q󰂅󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁qxxÀqyy󰂆󰂇Rqxy󰂁󰀑󰂇qxyU

SXxyIP󰂅qxxÀqyy󰂆󰂇IP󰂅qxxÀqyy󰂆P󰂇RqPxy󰂇qxyqyy

󰂅RS󰂆

theThisuppermusthalfbeofequalthesetoexpressions,!IÁ󰂉qxYqy󰂊󰁔we.Calculatingfind:

!Ifrom

󰀒qq󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰀓

xxII󰂈

P󰂅qxxÀqyy󰂆󰂇󰂅qxxÀqyy󰂆P󰂇RqPxy󰂇qP

!PxyIIq󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁P󰂅qxxÀqyy󰂆󰂇IP󰂅qxxÀqyy󰂆P󰂇RqPxy󰂅RT󰂆

which,bymultiplyingnumeratoranddenominatorbyIP󰂅qxxÀqyy󰂆ÀIq󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁P󰂅qÀq󰂁

xxyy󰂆P󰂇RqPxyYcanbesimplifiedto:

!Iq󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁I󰂈P󰂅qxx󰂇qyy󰂆󰂇

IP󰂅q󰂁

xxÀqyy󰂆P󰂇RqPxyX

󰂅RU󰂆

Fromthelowerhalfoftheseexpressions,wefind:!I󰂈

q󰀐

xyIP󰂅qxxÀqyy󰂆󰂇Iq󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂆P󰂇RqP󰂁󰀑P󰂅qxxÀqyyxy󰂇qxyqyy

qxy

󰂅RV󰂆

whichcanbeeasilysimplifiedto:

!I󰂈II

q󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁P󰂅qxx󰂇qyy󰂆󰂇󰂅qP󰂁

PxxÀqyy󰂆󰂇RqPxy

󰂅RW󰂆

󰂉areqSincebothexpressionsgivethesameresultfor!I,

xYexactlyqy󰂊󰁔isequivalent.

aneigenvectorofg.Therefore,bothmethodsitsItcorrespondingisnotdifficulteigenvaluetoderivethe!secondeigenvectorvPandP:

4vIP󰂅qxxÀqyy󰂆󰂇Iq󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁I󰂈

󰂅q󰂁5

xxÀqyy󰂆P󰂇RqPqPxy󰂅SH󰂆

4vIIP󰂈

P󰂅qxx

Àqq󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁5

yy󰂆ÀP󰂅qxxÀqyy󰂆P󰂇RqPqxy

󰂅SI󰂆

!q󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁I󰂈IP󰂅qxx󰂇qyy󰂆󰂇

IP󰂅q󰂆P󰂇RqP󰂁

xxÀqyyxy󰂅SP󰂆!Iq󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁P󰂈P󰂅qxx󰂇qyy󰂆À

IP󰂅q󰂁xxÀqyy󰂆P󰂇RqPxy

󰂅SQ󰂆

Notethat!Iisalwayslargerthanorequalto!PconfirmingthattheaveragegradientangleisalignedwithvI.TheDF,whichisperpendiculartothegradientisalignedwithvP.

APPENDIXB

EQUIVALENCE

goh

AND

󰁓tr

Bysubstituting(52)and(53),󰁓trisgivenby:

󰁓tr󰂈

!IÀ!P!qI󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂇!P

󰂈

󰂅q󰂁xxÀqyy󰂆P󰂇RqPxy

󰂅SR󰂆

qxx󰂇qyy

Ontheotherhand,goh󰀌isgivenby:

goh󰂈󰀌󰁐󰁐󰁗󰀌󰂅q󰀌sYxYqsYy󰂆󰀌󰂅SS󰂆

󰁗󰀌󰂅q󰀌sYxYqsYy󰂆

󰀌Ywhere,bysubstituting(4),

󰀌󰀌󰀌󰀌󰁘󰀌󰀌v󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰀌󰂅qsYxYqsYy󰂆󰀌u󰀌󰂈

2󰁘3P23P󰂁q󰁘sYx󰂇qsYy󰁗󰀌vu

󰂈

u󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰁗󰁗

t2󰁘3P2qP󰁘3P󰂁󰁗

xÀqPy󰂇Pqxqy󰁗

󰂈q󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂅q󰂁xxÀqyy󰂆P󰂇RqPxy

󰂅ST󰂆

and

󰁘󰀌󰀌󰂅q󰀌󰁘q󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁sYxYqsYy󰂆󰀌󰂈qP󰁗

sYx󰂇qP󰂁

󰁗

sYy

󰂈󰁘q󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂅qP󰁗

xÀqPy󰂆P󰂇󰂅Pqxqy󰂆P󰂁󰂈󰁘q󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁qRPPR󰂁

󰁗x󰂇Pqxqy󰂇qy󰂅SU󰂆

󰂈

󰁘q󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂅qP󰂁󰁗

x󰂇qPy󰂆P󰂈

󰁘

qP󰁗

x󰂇qP

󰂈qxx󰂇qyyX

Therefore,thecoherenceoftheaveragingmethodis

givenby:

918IEEETRANSACTIONSONPATTERNANALYSISANDMACHINEINTELLIGENCE,VOL.24,NO.7,JULY2002

q󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁󰂁Pgoh󰂈

󰂅qÀq󰂁xxyy󰂆P󰂇Rqxy

qxx󰂇qyy

󰂅SV󰂆

whichprovestheequivalenceofgohand󰁓tr.

APPENDIXC

ROTATIONOFSINGULARPOINTS

Itcanbeproventhat

󰁓hp󰁣oreY9󰂈󰁓hp󰁣oreYrefÁej9

󰂅SW󰂆

byusingpolarnotation󰂅&sY0s󰂆insteadof󰂅xYy󰂆forapositioninthereferencemodeloftheSPs.TheorientationoftheSDFisgivenby:

P󰀒󰁣oreYref󰂅&sY0s󰂆󰂈0s󰂇I

󰂅TH󰂆

andtheDFisgivenby:

󰀒󰁣oreYref󰂅&sY0s󰂆󰂈II

P0s󰂇R%X

󰂅TI󰂆TheproblemistodeterminetheSDFatposition󰂅&sY0s󰂆

afterrotationofthereferencemodeloveranangle9.Thesamplepointat󰂅&sY0s󰂆aftertherotationislocatedat󰂅&sY0sÀ9󰂆beforetherotation:

󰀒󰁣oreYref󰂅&sY0sÀ9󰂆󰂈IP󰂅0sÀ9󰂆󰂇I

R%X

󰂅TP󰂆

Therotationadds9totheorientationatthesamplepoint:

󰀒󰁣oreY9󰂅&sY0s󰂆󰂈II

P󰂅0sÀ9󰂆󰂇R%󰂇9X

󰂅TQ󰂆

Now,therotatedDFcanbeconvertedbacktothe

rotatedSDF:

P󰀒󰁣oreY9󰂅&sY0s󰂆󰂈󰂅0s󰂇I

P%󰂆󰂇9󰂈P󰀒󰁣oreYref󰂅&sY0s󰂆󰂇9󰂅TR󰂆

whichcompletestheproof.FromtheformulaitbecomesobviousthattheSDFmodelofacorehastoberotatedoverP%Followinginordertotheobtainsametheprocedureoriginalmodel.

foradelta,itcanbeproventhat

󰁓hp󰁣oreY9󰂈󰁓hp󰁣oreYrefÁejQ9X

󰂅TS󰂆

Now,theorientationoftheSDFisgivenby:

P󰀒delt󰁡Yref󰂅&sY0s󰂆󰂈À0s󰂇I

P%X

󰂅TT󰂆Followingthesameprocedureasforthecoregives:

󰀒delt󰁡Y9󰂅&sY0s󰂆󰂈ÀIP󰂅0sÀ9󰂆󰂇I

R%󰂇9

󰂅TU󰂆and:

P󰀒delt󰁡Y9󰂅&sY0s󰂆󰂈󰂅À0s󰂇I

P%󰂆󰂇Q9󰂈P󰀒delt󰁡Yref󰂅&sY0s󰂆󰂇Q9X󰂅TV󰂆

ThiscorrespondstothefactthatadeltahastoberotatedoverPQ%inordertoobtaintheoriginalmodel.

REFERENCES

[1]R.S.UsingGermain,ScienceTransformationA.Califano,ParameterandS.Clustering,ºColville,ªFingerprintIEEEMatching

[2]

R.DatabasesCappelli,andEng.,D.vol.Maio,4,no.and4,D.pp.ComputationalMaltoni,42-49,1997.

ªIndexingControl,forEfficient1:nMatching,ºProc.SixthFingerprintInt'l[3]

2000.

Automation,RoboticsandVision(ICARCV2000),Conf.Dec.J.DatabasesdeBoer,A.M.Bazen,andS.H.Gerez,ªIndexingFingerprint12th[4]2001.

Ann.WorkshopBasedonCircuits,MultipleSystemsFeatures,ºandSignalProc.Processing,ProRISC2001,Nov.T.[5]

KluwerLindeberg,A.M.AcademicScale-SpacePublishers,TheoryinComputerVision.Boston:FingerprintsBazenandGradients,ºBasedS.H.onGerez,thePrincipalªDirectional1994.

ComponentFieldAnalysisComputationofLocalfor[6]SystemsA.M.Images,ºBazenandSignalProc.ProRISC2000,11thAnn.WorkshopCircuits,andProcessing,S.H.Gerez,Nov.ªSegmentation2000.

[7]andProc.ProRISC2001,12thAnn.WorkshopCircuits,ofFingerprintE.R.Signal[8]

Routledge,Henry,Processing,ClassificationNov.2001.

SystemsandUsesofFingerPrints.London:A.M.DirectionalBazen1900.

andS.H.Gerez,ªExtractionofSingularPointsfromCTIT[9]Netherlands,WorkshopFieldsofFingerprints,ºMobileComm.inPerspective,K.pp.Mobile41-44,Comm.,Univ.ofTwente,Enschede,The[10]Recognition,KaruandA.K.Jain,Feb.ªFingerprint2001.

Classification,ºM.vol.29,no.3,pp.389-404,1996.

Pattern[11]PatternKawagoeM.M.S.Recognition,andA.Tojo,ªFingerprintPatternClassification,ºworkChong,T.H.vol.17,no.3,pp.295-303,1984.

[12]

vol.A.M.30,forno.FingerprintNgee,andR.K.L.Gay,ªGeometricFrame-9,pp.1475-1488,ImageClassification,ºPatternRecognition,forVideo-BasedFingerprintBazenandMatching,ºS.H.Gerez,1997.

Proc.ªAnThirdIntrinsicInt'lCoordinateConf.Audio-Systemand[13]

2001.

BiometricPersonAuthentication(AVBPA2001),JuneD.ªFVC2000:Maio,D.Maltoni,R.Cappelli,J.L.Wayman,andA.K.Jain,report,[14]

bias.csr.unibo.it/fvc2000/.

Univ.FingerprintofBologna,VerificationItaly,Sept.Competition,º2000,availableBiolabfrominternalhttp://G.A.NeuralDretsÈm,ªFingerprintFingerprintNetworkandH.G.Liljenstro

Subclassification:AS.B.andFaceApproach,ºRecognition,IntelligentBiometricTechniquesin[15]Press,Lee,andS.Tsutsui,eds.,pp.L.C.109-134,Jain,BocaU.Halici,Raton,I.Fla.:Hayashi,CRCC.L.FingerprintWilson,1999.

G.T.Candela,andC.I.Watson,ªNeural[16]no.Classification,ºJ.ArtificialNeuralNetworks,Networkvol.1,L.[17]FilterO'Gorman2,pp.203-228,M.Design,ºand1994.

PatternJ.V.Recognition,Nickerson,vol.ªAn22,ApproachtoFingerprintVision,Kass[18]Mar.Graphics,andA.Witkin,no.1,pp.29-38,1989.andImageªAnalyzingOrientedPatterns,ºComputerA.R.1987.

Processing,vol.37,no.3,pp.362-385,OrientedRaoandR.C.Jain,ªComputerizedFlowFieldAnalysis:[19]Intelligence,TextureFields,ºIEEETrans.PatternAnalysisandMachineN.FeatureRatha,S.vol.Chen,14,andno.A.7,pp.Jain,693-709,ªAdaptiveJulyFlow1992.

OrientationBased[20]vol.A.K.28,Extractionpp.inFingerprintImages,ºPatternRecognition,AuthenticationJain,L.1657-1672,Hong,[21]no.SystemS.Nov.UsingPankanti,1995.

Fingerprints,ºandR.Bolle,ªAnIdentity-P.9,pp.1365-1388,Sept.Proc.IEEE,vol.85,[22]vol.Perona,ªOrientationDiffusions,º1997.

IEEETrans.ImageProcessing,C.W.7,[23]Processing.Therrien,no.3,pp.457-467,Mar.1998.

O.UpperDiscreteSaddleRiver,RandomSignalsandStatisticalSignalbyNakamura,DirectionalK.DistributionGoto,andPatterns,ºT.Minami,N.J.:Prentice-Hall,1992.

Systems,ªFingerprintComputers,ClassificationControls,[24]vol.V.S.13,FingerprintSrinivasanno.5,pp.81-89,1982.

[25]

1992.

Images,ºandN.N.PatternMurthy,Recognition,ªDetectionvol.25,ofSingularno.2,pp.Points139-153,inA.K.BasedJain,S.Prabhakar,L.Hong,andS.Pankanti,ªFilterbank-no.5,pp.Fingerprint846-859,Matching,ºMay2000.

IEEETrans.ImageProcessing,vol.9,BAZENANDGEREZ:SYSTEMATICMETHODSFORTHECOMPUTATIONOFTHEDIRECTIONALFIELDSANDSINGULARPOINTSOF...919

[26]L.[27]Proc.HongJ.G.11thandScandinavianA.K.Jain,Conf.ªClassificationImageAnalysis,ofFingerprintImages,º

SignalProakis,1992.Processing.C.M.Rader,NewYork:F.Ling,MacmillanandC.L.Nikias,June1999.

PublishingAdvancedCompany,Digital

AskerelectricalM.Twente,engineeringBazenreceivedtheMScdegreeinresearchTheNetherlands,fromthein1998Universityforhisofprocessing,onhigh-resolutionparametricradaryearfinishingatThomson-CSFwhichhecontinuedforonemoreandhisPhDSignal.Currently,heisvariousSystemsthesisattheChairofSignalstopicsattheUniversityofTwenteonfingerprints,largematchingelasticallyingrobustdeformedminutiaeinfingerprintextractionrecognition,includ-fingerprints,fromandlow-quality

imagefingerprintprocessing,databases.patternrecognition,Otherresearchandcomputationalinterestsincludeindexingintelligence.

signalandSabihelectricalH.appliedengineeringGerezreceivedandthetheMScPhDdegreedegreeininThesciencesfromtheUniversityofTwente,tively.Netherlands,ElectricalHehasin1984and1989,respec-Twente1984-1989)asEngineeringworkedfortheDepartmentofanassistantattheUniverstityof1990).Startingandfromasanresearcher(intheperiod2001,assistantheprofessor(sinceSemiconductor,andDesignacademicCenterHengelo,activitiesThewithapositioniscombiningatNational

hisprocessing,teachingAlgorithmsforandinterestsVLSIcomputationalincludeDesignAutomationintelligence.designautomation,Netherlands.VLSIdesign,Hisresearchsignal(Wiley,Heis1999).

theauthorofthebookFpleaseFormorevisitourinformationDigitalLibraryonthisathttp://computer.org/publications/dlib.

oranyothercomputingtopic,

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文