文献翻译——指纹识别系统

第1页外文文献资料FingerprintRecognitionSystemFingerprintrecognitionsystemconsistofimagepreprocessing,featuresextractionandfeaturesmatchingthatrunseffectivelyandaccuratelyonpersonalcomputer.Theimagepreprocessingincludesnoiseremoval,histogramequalization,globalthresholdingandridgelinethinningwhicharenecessaryforthefeaturesextraction.Extractedfeaturesarethenstoredinafileforfingerprintmatching.Matchingalgorithmpresentedhereisasimple,fastandaccurate.Experimentalresultsformatchingareaccurate,reliableandfastforimplementationusingapersonalcomputerandfingerprintreader.Theproposedfingerprintalgorithmcanprovideaneffectivewayofautomatedidentificationandcanbeextendedtoothersecurityoridentificationapplications.FurtherthealgorithmcanbeimplantedonaFPGAplatformforarealtimepersonalautomatedidentificationsystem.1.INTRODUCTIONFingerprintrecognitionsystemsaretermedundertheumbrellaofbiometrics.Biometricrecognitionreferstothedistinctivephysiological(e.g.fingerprint,face,iris,retina)andbehavioral(e.g.signature,gait)characteristics,calledbiometricidentifiersorsimplybiometrics,forautomaticallyrecognizingindividuals.In1893,itwasdiscoveredthatnotwoindividualshavesamefingerprints.Afterthisdiscoveryfingerprintswereusedincriminalidentificationandtillnowfingerprintsareextensivelyusedinvariousidentificationapplicationsinvariousfieldsoflife.Fingerprintsaregraphicalflow-likeridgespresentonhumanfingers.Theyarefullyformedataboutseventhmonthoffetusdevelopmentandfingerprintconfigurationdonotchangethroughoutthelifeexceptduetoaccidentssuchasbruisesorcutonfingertips.Becauseofimmutabilityanduniqueness,theuseoffingerprintsforidentificationhasalwaysbeenofgreatinteresttopatternrecognitionresearchersandlawenforcementagencies.Conventionally,fingerprintrecognitionhasbeenconductedviaeitherstatisticalorsyntacticapproaches.Instatisticalapproacha第2页fingerprintsfeaturesareextractedandstoredinann-dimensionalfeaturevectoranddecisionmakingprocessisdeterminedbysomesimilaritymeasures.Insyntacticapproach,apatternisrepresentedasastring,tree1,orgraph2offingerprintfeaturesorpatternprimitivesandtheirrelations.Thedecisionmakingprocessisthensimplyasyntaxanalysisorparsingprocess.Thispapersuggeststhestatisticalapproach.Experimentalresultsprovetheeffectivenessofthismethodonacomputerplatform,hencemakingitsuitableforsecurityapplicationswitharelativelysmalldatabase.Thepreprocessingoffingerprintsiscarriedoutusingmodifiedbasicfilteringmethodswhicharesubstantiallygoodenoughforthepurposeofourapplicationswithreasonablecomputationaltime.BlockdiagramforthecompleteprocessisshowninFigure.1.2.IMAGEPREPROCESSINGFortheproperandtrueextractionofminutiae,imagequalityisimprovedandimagepreprocessingisnecessaryforthefeaturesextractionbecausewecannotextracttherequiredpointsfromtheoriginalimage.Firstofall,anysortofnoisepresentintheimageisremoved.Orderstatisticsfiltersareusedtoremovethetypeofnoisewhichoccursnormallyatimageacquisition.Afterwardsthefollowingimagepreprocessingtechniquesareappliedtoenhancethefingerprintimagesformatching.2.1HistogramEqualizationThismethodisusedwheretheunwantedpartoftheimageismadelighterinintensitysoastoemphasizethedesiredthedesiredpart.Figure2(a)showstheoriginalimage第3页andFigure2(b)histogramequalizationinwhichthediscontinuitiesinthesmallareasareremoved.Forthehistogramequalization,lettheinputandtheoutputlevelforanarbitrarypixelbeiandl,respectively.Thentheaccumulationofhistogramfrom0toi(0i255,0k255)isgivenbywhereH(k)isthenumberofpixelwithgraylevelk,i.e.histogramofanarea,andC(i)isalsoknownascumulativefrequency.2.2DynamicThresholdingBasicpurposeofthresholdingistoextracttherequiredobjectformthebackground.Thresholdingissimplythemappingofalldatapointshavinggraylevelmorethataveragegraylevel.TheresultsofthresholdingareshowninFigure3.2.3RidgelineThinning第4页Beforethefeaturescanbeextracted,thefingerprintshavetobethinnedorskeletonisedsothatallridgesareonepixelthick.Whenapixelisdecidedasaboundarypixel,itisdeleteddirectlyformtheimage3-5orflaggedandnotdeleteduntiltheentireimagebeenscanned6-7.Therearedeficienciesinbothcases.Intheformer,deletionofeachboundarypixelwillchangetheobjectintheimageandhenceaffecttheobjectsymmetrically.Toovercomethisproblem,somethinningalgorithmsuseseveralpassesinonethinningiteration.Eachpassisanoperationtoremoveboundarypixelsfromagivendirection.Pavlidis8andFieginandBen-Yosef9havedevelopedeffectivealgorithmsusingthismethod.However,boththetimecomplexityandmemoryrequirementwillincrease.Inthelatter,asthepixelsareonlyflagged,thestateofthebitmapattheendofthelastiterationwillusedwhendecidingwhichpixeltodelete.However,ifthisflagmapisnotusedtodecidewhetheracurrentpixelistobedeleted,theinformationgeneratedfromprocessingthepreviouspixelsincurrentiterationwillbelost.Incertainsituationsthefinalskeletonmaybebadlydistorted.Forexample,alinewithtwopixelsmaybecompletelydeleted.Recently,Zhou,QuekandNg10haveproposedanalgorithmthatsolvestheproblemdescribedearlierandisfoundtoperformsatisfactorilywhileprovidingareasonablecomputationaltime.ThethinningeffectisillustratedinFigure43.AhybridASICandFPGAArchitectureFPGAisEnglishFieldProgrammableGateArrayabbreviation,namelythesceneprogrammablegatearray,itistheproductwhichinPAL,GAL,EPLDandsoonintheprogrammablecomponentfoundationfurtherdevelops.Itistookinthespecial-purposeintegratedcircuit(ASIC)domainonekindpartlyhascustom-made,bothsolveshashadcustom-madetheelectriccircuitwhichtheelectriccircuitappears第5页theinsufficiency,andhasovercometheoriginalprogrammablecomponentgatenumberlimitedshortcoming.FPGAusedlogicalunitarrayLCA(LogicCellArray)thiskindofnewconcept,theinteriorincludinghasbeenpossibletodisposelogicalmoduleCLB(ConfigurableLogicBlock),outputloadmoduleIOB(InputOutputBlock)andinternalsegment(Interconnect)threeparts.TheFPGAessentialfeaturemainlyhas:1)UsesFPGAtodesigntheASICelectriccircuit,theuserdoesnotneedtothrowthepieceproduction,canobtainthechipwhichcomesinhandy.-2)FPGAmaymakeotheralltohavecustom-madeorpartlytohavecustom-madetheASICelectriccircuittheexperimentalpreview.2)TheFPGAinteriorhastherichtriggerandtheI/Opin.3)FPGAisintheASICelectriccircuitdesignsthecycletobeshortest,thedevelopmentcostislowest,oneofrisksmallestcomponents.4)FPGAisintheASICelectriccircuitdesignsthecycletobeshortest,thedevelopmentcostislowest,oneofrisksmallestcomponents.5)FPGAusesthehighspeedCHMOScraft,thepowerlossislow,mayandCMOS,theTTLleveliscompatible.Itcanbesaidthat,theFPGAchipisthesmallbatchsystemenhancesthesystemintegrationrate,oneofreliablebestchoices.FPGAisbydepositstheprocedureestablishesitsactivestatusininternalRAM,therefore,timeworkneedstocarryontheprogrammingtointernalRAM.Theusermayactaccordingtothedifferentdispositionpattern,selectsthedifferentprogrammingmethod.Whenaddstheelectricity,theFPGAchipthedataread-ininternalprogramsEPROMinRAM,afterthedispositioncompletes,FPGAthrustbuild-up.Afterfallstheelectricity,FPGArestorestheunsolderedglass,internallogicrelationsvanishing,therefore,FPGAcanuserepeatedly.TheFPGAprogrammingdoesnotneedthespecial-purposeFPGAprogrammer,onlymustusegeneralEPROM,thePROMprogrammerthen.WhenneedstorevisetheFPGAfunction,onlymusttradepieceofEPROMthen.Thus,identicalpieceFPGA,thedifferentprogrammingdata,mayhavethedifferentelectriccircuitfunction.ThereforetheFPGAuseisextremelyflexible.FPGAhasmanykindsofdispositionpattern:Parallelprincipal-mode-likeispieceofFPGAaddspieceofEPROMtheway;ThehostmaysupportpieceofPROMfromthepatterntoprogrammulti-pieceFPGA;第6页TheserialpatternmayuseserialPROMtoprogramFPGA;TheperipheralpatternmayFPGAtakethemicroprocessortheperipheral,programsbythemicroprocessortoit.TheembeddedFPGAblocksconsistofprogrammablelogicblocks,configurationlogic,testinterfacelogic,andsimplifiedIObuffersforuseindrivingandreceivingon-chipnets.MultipleenduserconfigurationmodearesupportedincludingFPGA,serialandparallelmodes.Individualcorescanbeconfiguredasynchronously,allowingfor“on-the-fly”reconfiguration.Todesignthenewhybridchips,amodifieddesignmethodologyisbeingdevelopedasshowninFigure10.1.Thishybriddesignflowincorporatestwoprovendesignmethodologies,theIBMASICflowandtheXILINXFPGAflow,includingseveralthirdpartyvendorsynthesisoptions.TheASICmethodologyintegratestheembeddedFPGAasahardcorewithappropriateASIClabelmodels.TheFPGAflow,includingtimingclosureoftheFPGAconfiguration,isdoneusingXILINXtools,thedesignerhasthechoiceofusingconstraintsordetailedtimingfromtheXilinxtoolflowtoclosetheASICtimingattheFPGAcoteinterfaces.IfanFPGAconfigurationisknownpriortothedesignoftheASIC,actualtiminginformationcanbepassedtotheASICtoolsfromtheFPGAtools.IfthelogiccontentoftheembeddedFPGAisunknown,theASICdesigncanbecompletedusingtimingassertionsandtheembeddedFPGAdesigncanbecompletedlater.IftheembeddedFPGAdesignisbeingreconfiguredaftertheASICisinmanufacturing,thefinaltimingconstraintsfromthecompletedASICcanbepassedtotheFPGAtoolsforthenewFPGAdesign.Thelogicdesignofthechipmustbepartitionedpriortofinalsynthesis.ThelogicdestinedforanFPGAblockisprocessedindependentlyofthelogicdesignforASIClogic.WhenmultipleFPGAlogicareused,eachmustbedesignedandoptimizedindependently.Thelogicaldesignofthechipmustbepartitionedpriortofinalsynthesis.ThelogicdestinedforanFPGAblockisprocessedindependentlyofthelogicdestinedforASIClogic.WhenmultipleFPGAlogicblocksareused,eachmustbedesignedandoptimizedindependently.TheASICphysicaldesignprocesstreatstheFPGAmacrosimilarlytoother第7页largeplaceableobjects,exceptforportassignment.DuringtheinitialASICdesign,theportassignmentofeachembeddedFPGAblockcanbemodifiedtoaccommodatefloorplanningortimingrequirements.OncethefinalASICdesignistape-out,theportassignmentsarefixedofsubsequentFPGAconfigurations.TheIBMASICmethodologyhasbeendescribedinreferences,andtheXilinxFPGAmethodologyisdescribedinreference.Astobeexpected,mostoftheissuesincrestingthehybridmethodologyoccurattheboundarybetweenthetwomethodologies.Themechanicsofthecommunicationsbetweenthetwostemscanbeaccomplishedbycreatingdatatranslators,however,optimizationbetweenthetwosystemscanbedifficult,duetothesignificantarchitecturaldifferencesbetweentraditionalASICflowsandtraditionalFPGAflows.4.FEATURESEXTRACTIONThetwobasicfeaturesextractedfromtheimageareridgeendingsandridgebifurcation.Forfingerprintimagesusedinautomatedidentification,ridgeendingsandbifurcationarereferredtoasminutiae.Todeterminethelocationofthesefeaturesinthefingerprintimage,a3x3windowmaskisused(Figure5).MisthedetectedpointandX1X8areitsneighboringpointsinaclockwisedirection.IfXnisablackpixel,thenitsresponseR(n)willbe1orotherwiseitwillbe0.IfMisanending,theresponseofthematrixwillbewhereR(9)=R(1).ForMtobeabifurcation,forexample,ifabifurcationisencounteredduringextraction,maskwillcontainthepixelinformationsuchasR(1)=R(3)=R(4)=R(6)=R(7)=0,R(2)=R(5)=R(8)=R(9)=1,and第8页Foralltheminutiaedetectedintheinterpolatedthinnedimage,thecoordinatesandtheirminutiaetypeissaveasfeaturefile.Attheendoffeatureextraction,afeaturerecordofthefingerprintisformed.Economically,theembeddedsolutioncanbethelessexpensiveoption.Aswewilldiscuss,theFPGAfabricdoesnotrequireanyuniquesemiconductorprocessingaboveandbeyondthebaseASIC(unlikeembeddedflashorembeddedDRAM).TheresultingincreaseinASICcostisassociatedwiththeareaoccupiedbytheembeddedFPGAcore.Inaddition,thecostofassembly,testandpackagingofasecongchipareeliminated.Incertaincases,itcanbeadvantageoustoincludeembeddedFPGAonanASICifthatFPGAeliminatestheneedforadditionaldesignpasses.Forexample,atvolumesofupto250000pieces,50KgatesofembeddedFPGAarecosteffectives.Similarly,10KgatesofembeddedFPGAarecosteffectiveversusa2passASICdesignatvolumeofupto1M.Ingeneral,ifmaskcostsrise,volumesdecrease,ormoredesignpassesareavoided,thentheembeddedFPGAapproachbecomesprogressivelymorecost-effectivecomparedtotheASICapproach.Thisisbecauseatlowvolumes,themaskcosts(andNRE)foradditionaldesignpassesbecomesasignificantaddertoper-chipcost,andthiscanoutweighthecostimpactofthelargerdiearearequiredbytheembeddedFPGAcircuitry.ThisanalysisleadsustoconcludethattechnologyandmarkettrendshavecreatedaneedforthedevelopmentofthehybridASIC/FPGAproduct.Maskcostsforadvancedtechnologiesaregrowingmarkingmultipledesignpassestoocostlyformany第9页applications.Fortunately,thetechnologyadvancementsthathavedriventhistrendhavealsoopenedupthepotentialtoembedsignificantamountsofFPGAgatesontoanASICdieenoughtohandlesomeofthedesignupdatesthatwouldotherwiserequireadditionaldesignpasses.5.MATCHINGFingerprintmatchingisthecentralpartofthispaper.Theproposedtechniqueisbasedonstructuralmodeloffingerprints11.Oneofthemajorbreakthroughsofthismethodisitsabilitytomachfingerprintsthatareshifted,rotatedandstretched.Thisisachievedbyadifferentmatchingapproach.Asitisclearthatthisalgorithmmatchesthetwofingerprintimagescapturedatdifferenttime.Thismatchingisbasedontheminutiaeidentificationandminutiaetypematching.Matchingprocedureiscomplexduetotwomainreasons;1)Theminutiaeofthefingerprintcapturedmayhavedifferentcoordinates2)Theshapeofthefingerprintcapturedatdifferenttimemaybedifferentduetostretching.Anautomatedfingerprintidentificationsystemthatisrobustmusthavefollowingcriteria:1)Sizeoffeaturesfilemustbesmall2)Algorithmmustbefastandrobust3)Algorithmmustberotationallyinvariant4)AlgorithmmustberelativelystretchinvariantToachievethesecriteria,thestructuralmatchingmethoddescribedbyHrechakandMcHugh11isadoptedasthebasisofourrecognitionalgorithm,withchangesmadetothealgorithm,toprovidemorereliableandimprovingoverallmatchingspeed.Thismatchingrepresentsthelocalidentificationapproach,inwhichlocalidentifiedfeatures,theirtypeandorientationissavedinfeaturesfile,iscorrelatedwiththeotherimagesextractedfeaturesfile.ThemodelisshowninFigure6.第10页Foreachextractedfeaturesonthefingerprint,aneighborhoodofsomespecifiedradiusRaboutthecentralfeatureisdefinedandthenEuclideandistanceandrelativeanglesbetweenthecentralpointandtheotherpointisnotedwiththepointstype.Sincethedistanceamongthepointremainsthesamethroughoutthelife.Sothistechniqueworkswellfortherotatedandshiftedimages.1,Bus:Weknowthatacircuitisalwaysmadebythedevicesconnectedbywires,inanalogcircuits,theconnectiondoesnotbecomeaproblembecausethedeviceisaserialrelationshipbetweenthegeneral,thedeviceisnotmuchconnectionbetweenthe,butthecomputerisnotthesamecircuit,itisamicroprocessorcore,thedevicemustbeconnectedwiththemicroprocessor,thedevicemustbecoordinationbetween,sotheyneedtoconnectonalot,asifstillanalogcircuitlikethemicroprocessoranddevicesintheconnectionbetweentheindividual,thenumberoflineswillbealittlemoresurprising,thereforetheintroductionofthemicroprocessorbus概念ZhongEachdeviceGongtongaccessconnections,alldevices8Shujulineallreceivedeightpubliconline,thatistheequivalentofalldevicestogetherinparallel,butonlythisdoesnotwork,iftherearetwodevicessenddataatthesametime,a0,a1,then,whetherthereceiverreceivedwhatisit?第11页Thissituationisnotallowed,sotobecontrolledbycontrollingtheline,time-sharingthedevicetoworkatanytimeonlyonedevicetosenddata(whichcanhavemultipledevicestoreceiveboth).Devicesdataconnectionisknownasthedatabus,thedeviceiscalledlineofcontrolallthecontrolbus.Internalorexternalmemoryinthemicrocontrollerandotherdeviceshavememorycells,thememorycelltobeassignedaddresses,youcanuse,distribution,ofcourse,toaddressgivenintheformofelectricalsignals,andasmorememorycells,so,fortheaddressallocationThelineisalsomoreoftheselinesiscalledtheaddressbus.Second,data,address,command:Thereasonwhythesethreetogetherbecauseofthenatureofthesethreearethesame-thenumber,orareastringof0and1formthesequence.Inotherwords,addresses,instructionsarealsodata.Instruction:fromsinglechipdesignerprovidesanumberofcommonlyusedinstructionswithmnemonicwehaveastrictcorrespondencebetweenthedevelopercannotbechangedbytheMCU.Address:thesearchforMCUinternal,externalstorageunits,inputandoutputportbasedontheaddressoftheinternalunitvalueprovidedbythechipdesignerisgood,cannotbechanged,theexternalunitcanbesinglechipdeveloperstodecide,butthereareanumberofaddressunitsisamust(seeproceduresfortheimplementationoftheprocess).Third,P0port,P2andP3ofthesecondfunctionIuse:BeginnersoftenontheP0port,P2andP3portIusethesecondfunctionpuzzledthatthesecondfunctionandhaveaswitchbetweentheoriginalfunctionoftheprocess,orhaveadirective,infact,theportThesecondfeatureisautomatic,donotneedinstructionstoconvert.SuchasP3.6,P3.7respectivelyWR,RDsignal,whenthemicrochipprocessingmachinesexternalRAMorexternalI/Oport,theyareusedasasecondfunction,notasageneral-purposeI/Oportused,solongasaAmicroprocessorimplementationoftheMOVXinstruction,therewillbeacorrespondingsignalsentfromtheP3.6orP3.7,noprioruseofcommands.Infactnotasageneral-purposeI/Oportuseisalsonotanobut(user)notasageneral-purposeI/Oporttouse.YoucanarrangetheorderofaSETBP3.7sinstructions,andwhentheMCUexecutiontotheinstruction,thealsomakeP3.7intoahigh,butuserswillnotdosobecausethisisusuallywillcausethesystemtocollapse.Fourth,theprogramsimplementation:Reductioninpowerafterthe8051microcontrollerwithintheprogramcounter(PC)inthevalueof0000,theprocess第12页isalwaysfromthe0000unitsstarted,thatis:thesystemmustexistinROM0000thisunit,andin0000unitmustbestoredinasingleinstruction.5,thestack:Stackisaregion,isusedtostoredata,thereisnospecialabouttheregionitselfisapartofinternalRAM,specialaccesstoitsdatastorageandthewaythattheso-calledadvancedpostoutbackwardfirstout,andthestackhasaspecialdatatransmissioninstructionsthatPUSHandPOP,hasaspecialexpertiseinitsservicesunit,thatis,thestackpointerSP,wheneveraPUSHinstructionexecution,SPon(intheBasedontheoriginalvalue)automaticallyadd1,whenevertheimplementationofaPOPinstruction,SPwill(onthebasisoftheoriginalvalue)automaticallyby1.AstheSPvaluescanbechangedwiththeinstructions,solongasthebeginningoftheprocesstochangethevalueoftheSP,youcansetthestackmemoryunitrequired,suchastheprogrambegins,withanMOVSP,#5FHinstructionsWhensetonthestackstartingfromthememoryunit60Hunit.Thereisalwaysthebeginningofthegeneralprocedurewithsuchadirectivetosetthestackpointer,becauseboot,SPinitialvalueof07H,08HThisunitfromthebeginningtostacknext,and08Hto1FH8031isthesecondintheregion,threeorfourworkingregisterarea,oftenused,thiswillleadtoconfusionofdata.Differentau