On-Line Fingerprint Verification.pdf
【机械类毕业论文中英文对照文献翻译】对齐点模式匹配
收藏
资源目录
压缩包内文档预览：
编号：77689902
类型：共享资源
大小：1.45MB
格式：RAR
上传时间：2020-05-07
上传人：柒哥
认证信息
个人认证
杨**（实名认证）
湖南
IP属地：湖南
6
积分
- 关 键 词：
-
机械类毕业论文中英文对照文献翻译
机械类
毕业论文
中英文
对照
文献
翻译
对齐
模式
匹配
- 资源描述：
-
【机械类毕业论文中英文对照文献翻译】对齐点模式匹配,机械类毕业论文中英文对照文献翻译,机械类,毕业论文,中英文,对照,文献,翻译,对齐,模式,匹配
- 内容简介：
-
302IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 19, NO. 4, APRIL 1997On-Line Fingerprint VerificationAnil Jain, Fellow, IEEE, Lin Hong, and Ruud Bolle, Fellow, IEEEAbstractFingerprint verification is one of the most reliable personal identification methods. However, manual fingerprintverification is so tedious, time-consuming, and expensive that it is incapable of meeting todays increasing performancerequirements. An automatic fingerprint identification system (AFIS) is widely needed. It plays a very important role in forensic andcivilian applications such as criminal identification, access control, and ATM card verification. This paper describes the design andimplementation of an on-line fingerprint verification system which operates in two stages: minutia extraction and minutia matching.An improved version of the minutia extraction algorithm proposed by Ratha et al., which is much faster and more reliable, isimplemented for extracting features from an input fingerprint image captured with an on-line inkless scanner. For minutia matching,an alignment-based elastic matching algorithm has been developed. This algorithm is capable of finding the correspondencesbetween minutiae in the input image and the stored template without resorting to exhaustive search and has the ability of adaptivelycompensating for the nonlinear deformations and inexact pose transformations between fingerprints. The system has been testedon two sets of fingerprint images captured with inkless scanners. The verification accuracy is found to be acceptable. Typically, acomplete fingerprint verification procedure takes, on an average, about eight seconds on a SPARC 20 workstation. Theseexperimental results show that our system meets the response time requirements of on-line verification with high accuracy.Index TermsBiometrics, fingerprints, matching, verification, minutia, orientation field, ridge extraction. 1INTRODUCTIONINGERPRINTS are graphical flow-like ridges present onhuman fingers. They have been widely used in personalidentification for several centuries 11. The validity of theiruse has been well established. Inherently, using currenttechnology fingerprint identification is much more reliablethan other kinds of popular personal identification methodsbased on signature, face, and speech 11, 3, 15. Al-though fingerprint verification is usually associated withcriminal identification and police work, it has now becomemore popular in civilian applications such as access control,financial security, and verification of firearm purchasersand driver license applicants 11, 3. Usually, fingerprintverification is performed manually by professional finger-print experts. However, manual fingerprint verification isso tedious, time-consuming, and expensive that it does notmeet the performance requirements of the new applica-tions. As a result, automatic fingerprint identification sys-tems (AFIS) are in great demand 11. Although significantprogress has been made in designing automatic fingerprintidentification systems over the past 30 years, a number ofdesign factors (lack of reliable minutia extraction algorithms,difficulty in quantitatively defining a reliable match betweenfingerprint images, fingerprint classification, etc.) create bot-tlenecks in achieving the desired performance 11.An automatic fingerprint identification system is con-cerned with some or all of the following issues: Fingerprint Acquisition: How to acquire fingerprint im-ages and how to represent them in a proper format. Fingerprint Verification: To determine whether twofingerprints are from the same finger. Fingerprint Identification: To search for a query finger-print in a database. Fingerprint Classification: To assign a given fingerprintto one of the prespecified categories according to itsgeometric appearance.A number of methods are used to acquire fingerprints.Among them, the inked impression method remains themost popular. It has been essentially a standard techniquefor fingerprint acquisition for more than 100 years 3. Thefirst step in capturing an inked impression of a fingerprintis to place a few dabs of ink on a slab then rolling it outsmoothly with a roller until the slab is covered with a thin,even layer of ink. Then the finger is rolled from one side ofthe nail to the other side over the inked slab which inks theridge patterns on top of the finger completely. After that,the finger is rolled on a piece of paper so that the inked im-pression of the ridge pattern of the finger appears on thepaper. Obviously, this method is time-consuming and un-suitable for an on-line fingerprint verification system. In-kless fingerprint scanners are now available which are ca-pable of directly acquiring fingerprints in digital form. Thismethod eliminates the intermediate digitization process ofinked fingerprint impressions and makes it possible tobuild an on-line system. Fig. 1 shows the two inkless fin-gerprint scanners used in our verification system. Finger-print images captured with the inked impression methodand the inkless impression method are shown in Fig. 2.0162-8828/97$10.00 1997 IEEE A. Jain and L. Hong are with the Pattern Recognition and Image Process-ing Laboratory, Department of Computer Science, Michigan State Univer-sity, East Lansing, MI 48824. E-mail: jain, honglin. R. Bolle is with the Exploratory Computer Vision Group, IBM T.J. WatsonResearch Center, Yorktown Heights, NY 10598. E-mail: bolle.Manuscript received Feb. 2, 1996; revised Oct. 21, 1996. Recommended for accep-tance by B. Dom.For information on obtaining reprints of this article, please send e-mail to:transpami, and reference IEEECS Log Number P96113.FJAIN ET AL.: ON-LINE FINGERPRINT VERIFICATION303(a)(b)Fig. 1. Inkless fingerprint scanners: (a) Manufactured by Identix.(b) Manufactured by Digital Biometrics.(a)(b)Fig. 2. Comparison of fingerprint images captured by different meth-ods. (a) Inked impression method (from NIST database). (b) Inklessimpression method (with a scanner manufactured by Digital Biometrics). (a) (b) (c) (d) (e) (f)Fig. 3. A coarse-level fingerprint classification into six categories:(a) Arch. (b) Tented arch. (c) Right loop. (d) Left loop. (e) Whorl. (f) Twinloop.The goal of fingerprint classification is to assign a givenfingerprint to a specific category according to its geometricproperties (Fig. 3 shows a coarse-level fingerprint classifi-cation). The main purpose of fingerprint classification is tofacilitate the management of large fingerprint databasesand to speedup the process of fingerprint matching. Gener-ally, manual fingerprint classification is performed within aspecific framework such as the well-known Henry system3. Different frameworks use different sets of properties.However, no matter what type of framework is used, theclassification is based on ridge patterns, local ridge orienta-tions and minutiae. Therefore, if these properties can bedescribed quantitatively and extracted automatically from afingerprint image then fingerprint classification will be-come an easier task. During the past several years, a num-ber of researchers have attempted to solve the fingerprintclassification problem 11, 3, 9, 10, 26. Unfortunately,their efforts have not resulted in the desired accuracy. Algo-rithms reported in the literature classify fingerprints into fiveor six categories with about 90 percent classification accuracyon a medium size test set (several thousand images) 9, 10,26. However, to achieve a higher recognition accuracy witha large number of categories still remains a difficult problem.Fingerprint verification determines whether two finger-prints are from the same finger or not. It is widely believedthat if two fingerprints are from the same source, then theirlocal ridge structures (minutia details) match each othertopologically 11, 3. Eighteen different types of local ridgedescriptions have been identified 11. The two mostprominent structures are ridge endings and ridge bifurca-tions which are usually called minutiae. Fig. 4 shows ex-amples of ridge endings and ridge bifurcations. Based onthis observation and by representing the minutiae as apoint pattern, an automatic fingerprint verification problemmay be reduced to a point pattern matching (minutiamatching) problem. In the ideal case, if1) the correspondences between the template and inputfingerprint are known,2) there are no deformations such as translation, rotationand nonlinear deformations, etc. between them, and3) each minutia present in a fingerprint image is exactlylocalized, then fingerprint verification consists of thetrivial task of counting the number of spatiallymatching pairs between the two images.Fig. 4. Ridge ending and ridge bifurcation.However, in practice1) no correspondence is known beforehand,2) there are relative translation, rotation and nonlineardeformations between template minutiae and inputminutiae,3) spurious minutiae are present in both templates andinputs, and4) some minutiae are missed.Therefore, in order for a fingerprint verification algorithmto operate under such circumstances, it is necessary toautomatically obtain minutia correspondences, to recoverdeformations, and to detect spurious minutiae from finger-print images. Unfortunately, this goal is quite difficult toachieve. Fig. 5 illustrates the difficulty with an example oftwo fingerprint images of the same finger.304IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 19, NO. 4, APRIL 1997Fig. 5. Two different fingerprint images from the same finger. In orderto know the correspondence between the minutiae of these two finger-print images, all the minutiae must be precisely localized and the de-formations must be recovered.Fingerprint identification refers to the process ofmatching a query fingerprint against a given fingerprintdatabase to establish the identity of an individual. Its goalis to quickly determine whether a query fingerprint ispresent in the database and to retrieve those which aremost similar to the query from the database. The criticalissues here are both retrieval speed and accuracy. In fact,this problem relates to a number of techniques studiedunder the auspices of computer vision, pattern recogni-tion, database, and parallel processing. Operational fin-gerprint retrieval systems are being used by various lawenforcement agencies 11.In this paper, we will introduce an on-line fingerprintverification system whose purpose is to capture finger-print images using an inkless scanner and to comparethem with those stored in the database in “real time.”Such a system has great utility in a variety of personalidentification and access control applications. The overallblock diagram of our system is shown in Fig. 6. It operatesas follows:1) Off-line phase: Several impressions (depending on thespecification of the system) of the fingerprint of a per-son to be verified are first captured and processed bya feature extraction module; the extracted features arestored as templates in a database for later use;2) On-line phase: The individual to be verified giveshis/her identity and places his/her finger on the in-kless fingerprint scanner, minutia points are extractedfrom the captured fingerprint image; these minutiaeare then fed to a matching module, which matchesthem against his/her own templates in the database.Fig. 6. Overview of our on-line fingerprint verification system.The following two modules are the main components ofour on-line fingerprint verification system: Minutiae extraction. Minutiae are ridge endings orridge bifurcations. Generally, if a perfect segmenta-tion can be obtained, then minutia extraction is just atrivial task of extracting singular points in a thinnedridge map. However, in practice, it is not always pos-sible to obtain a perfect ridge map. Some global heu-ristics need to be used to overcome this limitation. Minutia matching. Minutia matching, because of de-formations in sensed fingerprints, is an elasticmatching of point patterns without knowing theircorrespondences beforehand. Generally, finding thebest match between two point patterns is intractableeven if minutiae are exactly located and no deforma-tions exist between these two point patterns. The ex-istence of deformations makes the minutia matchingmuch more difficult.For segmentation and minutia extraction, a modifiedversion of the minutia extraction algorithm proposed in 18is implemented which is much faster and more reliable forminutia extraction. We propose a hierarchical approach toobtain a smooth orientation field estimate of the input fin-gerprint image, which greatly improves the performance ofminutia extraction. For minutia matching, we propose analignment-based elastic matching algorithm. This algorithmis capable of finding the correspondences between minutiaewithout resorting to an exhaustive search and has the abil-ity to adaptively compensate for the nonlinear deforma-tions and inexact pose transformations between differentfingerprints. Experimental results show that our systemachieves excellent performance in a real environment.In the following sections we will describe in detail ouron-line fingerprint verification system. Section 2 mainlydiscusses the fingerprint feature extraction module. Sec-tion 3 presents our minutia matching algorithm. Experi-mental results on two fingerprint databases captured withtwo different inkless scanners are described in Section 4.Section 5 contains the summary and discussion.2MINUTIAEXTRACTIONIt is widely known that a professional fingerprint examinerrelies on minute details of ridge structures to make finger-print identifications 11, 3. The topological structure ofthe minutiae of a fingerprint is unique, and invariant withaging and impression deformations 11, 3. This impliesthat fingerprint identification can be based on the topologi-cal structural matching of these minutiae. This reduces thecomplex fingerprint verification to minutia matching proc-ess which, in fact, is a sort of point pattern matching withthe capability of tolerating, to some restricted extent, de-formations of the input point patterns. Therefore, the firststage in an automatic fingerprint verification procedure isto extract minutiae from fingerprints. In our on-line finger-print verification system, we have implemented a minutiaextraction algorithm which is an improved version of themethod proposed by Ratha et al. 18. Its overall flowchartis depicted in Fig. 7. We assume that the resolution of inputfingerprint images is 500 dpi.JAIN ET AL.: ON-LINE FINGERPRINT VERIFICATION305Fig. 7. Flowchart of the minutia extraction algorithm.2.1 Estimation of Orientation FieldA number of methods have been proposed to estimate theorientation field of flow-like patterns 17. In our system, anew hierarchical implementation of Raos algorithm 17 isused. Raos algorithm consists of the following main steps:1) Divide the input fingerprint image into blocks of sizeW W.2) Compute the gradients Gx and Gy at each pixel in eachblock.3) Estimate the local orientation of each block using thefollowing formula:qoxyjWiWxyjWiWG i j G i jGi jGi j=-FHGGGIKJJJ-=1221112211tan,c h c hc hc hej(1)where W is the size of the block, and Gx and Gy arethe gradient magnitudes in x and y directions, re-spectively.The orientation field of a good quality fingerprint imagecan be reasonably estimated with this algorithm. However,the presence of high-curvature ridges, noise, smudges, andbreaks in ridges leads to a poor estimate of the local orien-tation field. A postprocessing procedure needs to be ap-plied to overcome this limitation. In our system, the fol-lowing iterative steps are added to improve an inconsistentorientation field: Compute the consistency level of the orientation fieldin the local neighborhood of a block (i, j) with thefollowing formula:CNiji joi jD= - 12qq,bg b gbg(2) -= -+082. However, thepresence of undesired spikes and breaks present in athinned ridge map may lead to many spurious minutiaebeing detected. Therefore, before the minutia detection, asmoothing procedure is applied to remove spikes and tojoin broken ridges. Our ridge smoothing algorithm uses thefollowing heuristics: If a branch in a ridge map is roughly orthogonal tothe local ridge directions and its length is less than aspecified threshold Tb, then it will be removed. If a break in a ridge is short enough and no otherridges pass through it, then it will be connected.Although the above heuristics do delete a large percentageof spurious minutiae, many spurious minutiae still survive.The reason is that the above processing relies on local ridgeinformation. If this information itself is unreliable, then theabove heuristics have no way of differentiating false minu-tiae from true minutiae. Therefore, a refinement which isbased on structural information is necessary. Our refine-ment algorithm eliminates the spurious minutiae based onthe following rules: If several minutiae form a cluster in a small region,then remove all of them except for the one nearest tothe cluster center. If two minutiae are located close enough, facing eachother, but no ridges lie between them, then removeboth of them. (a) Input image. (b) Orientation field. (c) Fingerprint region. (d) Ridge map. (e) Thinned ridge map. (f) extracted minutiae.Fig. 9. Results of our minutia extraction algorithm on a fingerprint im-age (512 512) captured with an inkless scanner. (a) Input image.(b) Orientation field superimposed on the input image. (c) Fingerprintregion. (d) Extracted ridges. (e) Thinned ridge map. (f) Extracted minu-tiae and their orientations superimposed on the input image.JAIN ET AL.: ON-LINE FINGERPRINT VERIFICATION307After the above refinement procedure is performed, thesurviving minutiae are treated as true minutiae. Althoughthe above heuristics can not ensure a perfect location ofeach minutia, they are able to delete several spurious mi-nutiae. For each surviving minutia, the following parame-ters are recorded:1) x-coordinate,2) y-coordinate,3) orientation which is defined as the local ridge orien-tation of the associated ridge, and4) the associated ridge.The recorded ridges are represented as one-dimensionaldiscrete signals which are normalized by the average inter-ridge distance. These recorded ridges are used for align-ment in the minutia matching phase. Fig. 9 shows the re-sults of our minutia extraction algorithm on a fingerprintimage captured with an inkless scanner.3MINUTIAMATCHINGGenerally, an automatic fingerprint verification/identifica-tion is achieved with point pattern matching (minutiaematching) instead of a pixel-wise matching or a ridge pat-tern matching of fingerprint images. A number of pointpattern matching algorithms have been proposed in theliterature 23, 1, 21, 16. Because a general pointmatching problem is essentially intractable, features associ-ated with each point and their spatial properties such as therelative distances between points are often used in these al-gorithms to reduce the exponential number of search paths.The relaxation approach 16 iteratively adjusts the con-fidence level of each corresponding pair based on its con-sistency with other pairs until a certain criterion is satisfied.Although a number of modified versions of this algorithmhave been proposed to reduce the matching complexity23, these algorithms are inherently slow because of theiriterative nature.The Hough transform-based approach proposed byStockman et al. 22 converts point pattern matching to aproblem of detecting the highest peak in the Hough spaceof transformation parameters. It discretizes the transforma-tion parameter space and accumulates evidence in the dis-cretized space by deriving transformation parameters thatrelate two point patterns using a substructure or featurematching technique. Karu and Jain 8 proposed a hierar-chical Hough transform-based registration algorithm whichgreatly reduced the size of accumulator array by a mul-tiresolution approach. However, if the number of minutiapoint is less than 30, then it is very difficult to accumulateenough evidence in the Hough transform space for a reli-able match.Another approach to point matching is based on energyminimization. This approach defines a cost function basedon an initial set of possible correspondences and uses anappropriate optimization algorithm such as genetic algo-rithm 1 and simulated annealing 21 to find a possiblesuboptimal match. These methods tend to be very slow andare unsuitable for an on-line fingerprint verification system.In our system, an alignment-based matching algorithm isimplemented. Recognition by alignment has received agreat deal of attention during the past few years 12, be-cause it is simple in theory, efficient in discrimination, andfast in speed. Our alignment-based matching algorithmdecomposes the minutia matching into two stages:1) Alignment stage, where transformations such astranslation, rotation and scaling between an input anda template in the database are estimated and the inputminutiae are aligned with the template minutiae ac-cording to the estimated parameters; and2) Matching stage, where both the input minutiae and thetemplate minutiae are converted to polygons in thepolar coordinate system and an elastic string match-ing algorithm is used to match the resulting polygons.3.1 Alignment of Point PatternsIdeally, two sets of planar point patterns can be alignedcompletely by two corresponding point pairs. A truealignment between two point patterns can be obtained bytesting all possible corresponding point pairs and selectingthe optimal one. However, due to the presence of noise anddeformations, the input minutiae cannot always be alignedexactly with respect to those of the templates. In order toaccurately recover pose transformations between two pointpatterns, a relatively large number of corresponding pointpairs need to be used. This leads to a prohibitively largenumber of possible correspondences to be tested. Therefore,an alignment by corresponding point pairs is not practicaleven though it is feasible.Fig. 10. Alignment of the input ridge and the template ridge.It is well known that corresponding curve segments arecapable of aligning two point patterns with a high accuracyin the presence of noise and deformations. Each minutia ina fingerprint is associated with a ridge. It is clear that a truealignment can be achieved by aligning correspondingridges (see Fig. 10). During the minutiae detection stage,when a minutia is extracted and recorded, the ridge onwhich it resides is also recorded. This ridge is representedas a planar curve with its origin coincident with the minutiaand its x-coordinate being in the same direction as the di-rection of the minutia. Also, this planar curve is normalizedwith the average inter-ridge distance. By matching theseridges, the relative pose transformation between the inputfingerprint and the template can be accurately estimated.To be specific, let Rd and RD denote the sets of ridges asso-308IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 19, NO. 4, APRIL 1997ciated with the minutiae in input image and template, re-spectively. Our alignment algorithm can be described interms of the following steps:1) For each ridge d Rd, represent it as an one-dimensional discrete signal and match it against eachridge, D RD according to the following formula:SdDd DiiiLiiiL=0220(7)where L is the minimal length of the two ridges and diand Di represent the distances from point i on theridges d and D to the x-axis, respectively. The sam-pling interval on a ridge is set to the average inter-ridge distance. If the matching score S (0 S 1) islarger than a certain threshold Tr, then go to step 2,otherwise continue to match the next pair of ridges.2) Estimate the pose transformation between the tworidges (Fig. 10). Generally, a least-square method canbe used to estimate the pose transformation. How-ever, in our system, we observe that the followingmethod is capable of achieving the same accuracy withless computation. The translation vector (Dx, Dy)T be-tween the two corresponding ridges is computed byDDxyxyxyddDDFHIK=FHGIKJ-FHGIKJ(8)where (xd, yd)T and (xD, yD)T are the x and y coordi-nates of the two minutiae, which are called referenceminutiae, associated with the ridges d and D, respec-tively. The rotation angle Dq between the two ridgesis computed byDGqg=-=10LiiiLch(9)where L is the minimal length of the two ridges d andD; gi and Gi are radial angles of the ith point on theridge with respect to the reference minutia associatedwith the two ridges d and D, respectively. The scalingfactor between the input and template images is as-sumed to be one. This is reasonable, because finger-print images are captured with the same device inboth the off-line processing phase and the on-lineverification phase.3) Denote the minutia (xd, yd, qd)T, based on which thepose transformation parameters are estimated, as thereference minutia. Translate and rotate all the N inputminutiae with respect to this reference minutia, ac-cording to the following formula:xyxyxxyyiAiAiAidididqqqqqqqqFHGGGIKJJJ=FHGGIKJJ+-FHGIKJ-FHGGGIKJJJDDDDDDDcossinsincos00001(10)where (xi, yi, qi)T, (i = 1, 2, ., N), represents an inputminutia and xyiAiAiAT,qej represents the corre-sponding aligned minutia.3.2 Aligned Point Pattern MatchingIf two identical point patterns are exactly aligned with eachother, each pair of corresponding points is completely coin-cident. In such a case, a point pattern matching can be sim-ply achieved by counting the number of overlapping pairs.However, in practice, such a situation is not encountered.On the one hand, the error in determining and localizingminutia hinders the alignment algorithm to recover therelative pose transformation exactly, while on the otherhand, our alignment scheme described above does notmodel the nonlinear deformation of fingerprints which isan inherent property of fingerprint impressions. With theexistence of such a nonlinear deformation, it is impossibleto exactly recover the position of each input minutia withrespect to its corresponding minutia in the template. There-fore, the aligned point pattern matching algorithm needs tobe elastic which means that it should be capable of tolerat-ing, to some extent, the deformations due to inexact extrac-tion of minutia positions and nonlinear deformations. Usu-ally, such an elastic matching can be achieved by placing abounding box around each template minutia, which speci-fies all the possible positions of the corresponding inputminutia with respect to the template minutia, and restrict-ing the corresponding minutia in the input image to bewithin this box 18. This method does not provide a satis-factory performance in practice, because local deformationsmay be small while the accumulated global deformationscan be quite large. We have implemented an adaptive elas-tic matching algorithm with the ability to compensate theminutia localization errors and nonlinear deformations.LetPxyxyPPPTMPMPMPT=FHIK111, .,qqejejdenote the set of M minutiae in the template andQxyxyQQQTNQNQNQT=FHIK111, .,qqejejdenote the set of N minutiae in the input image which isaligned with the above template with respect to a givenreference minutia point. The steps in our elastic point pat-tern matching algorithm are given below:1) Convert each minutia point to the polar coordinatesystem with respect to the corresponding referenceminutia on which the alignment is performed:rexxyyyyxxiiiiririririrqqqFHGGIKJJ=-+-FHGIKJ-FHGGGGGGIKJJJJJJ*-*ej ej221tan(11)wherexyiii*, qej are the coordinates of a minutia,JAIN ET AL.: ON-LINE FINGERPRINT VERIFICATION309(xr, yr, qr)T are the coordinates of the reference minu-tia, and (ri, ei, qi)T is the representation of the minutiain polar coordinate system (ri represents the radialdistance, ei represents the radial angle, and qi repre-sents the orientation of the minutia with respect to thereference minutia).2) Represent the template and the input minutiae in thepolar coordinate system as symbolic strings by con-catenating each minutia in the increasing order of ra-dial angles:PrerepPPPTMPMPMPT=FHIK111, .,qqejej(12)QrerepQQQTNQNQNQT=FHIK111, .,qqejej(13)whererePPP*,qej and reQQQ*,qej represent the cor-responding radius, radial angle, and normalized mi-nutia orientation with respect to the reference minu-tia, respectively.3) Match the resulting strings Pp and Qp with a dynamic-programming algorithm 4 to find the edit distancebetween Pp and Qp which is described below.4) Use the edit distance between Pp and Qp to establishthe correspondence of the minutiae between Pp andQp. The matching score, Mpq, is then computed ac-cording to the following formula:MNM Npqpair=100max,kp(14)where Npair is the number of the minutiae which fall inthe bounding boxes of template minutiae. The maxi-mum and minimum values of the matching score are100 and 1, respectively. The former value indicates aperfect match, while the later value indicates nomatch at all.Minutia matching in the polar coordinate has several ad-vantages. We have observed that the nonlinear deformationof fingerprints has a radial property. In other words, thenonlinear deformation in a fingerprint impression usuallystarts from a certain point (region) and nonlinearly radiatesoutward. Therefore, it is beneficial to model it in the polarspace. At the same time, it is much easier to formulate rota-tion, which constitutes the main part of the alignment errorbetween an input image and a template, in the polar spacethan in the Cartesian space. The symbolic string generatedby concatenating points in an increasing order of radialangle in polar coordinate uniquely represents a point pat-tern. This reveals that the point pattern matching can beachieved with a string matching algorithm.A number of string matching algorithms have been re-ported in the literature 4. Here, we are interested in incor-porating an elastic criteria into a string matching algorithm.Generally, string matching can be thought of as the maxi-mization/minimization of a certain cost function such asthe edit distance. Intuitively, including an elastic term inthe cost function of a string matching algorithm can achievea certain amount of error tolerance. Given two strings Ppand Qp of lengths M and N, respectively, the edit distance,C(M, N), in our algorithm is recursively defined with thefollowing equations:C m nmnC mnC m nC mnw m nmMnN,min,afafafafaf=-+-+-+RS|T|UV|W|RS|T|000111100if or andWW(15)w m nrrerremPnQmPnQ,af=-+-RS|T|abg qdqeDDDDWif and otherwise?(16)DeaaeeamPnQ=-+-RS|T|ifotherwise360360180180ejejmod(17)Dqqq=-+-RS|T|aaamPnQifotherwise360360180180ejejmod(18)where a, b, and g are the weights associated with eachcomponent, respectively; d,?, and e specify the boundingbox; and W is a pre-specified penalty for a mismatch. Suchan edit distance, to some extent, captures the elastic prop-erty of string matching. It represents a cost of changing onepolygon to the other. However, this scheme can only toler-ate, but not compensate for, the adverse effect on matchingproduced by the inexact localization of minutia and nonlin-ear deformations. Therefore, an adaptive mechanism isneeded. This adaptive mechanism should be able to trackthe local nonlinear deformation and inexact alignment andtry to alleviate them during the minimization process.However, we do not expect that this adaptive mechanismcan handle the “order flip” of minutiae, which, to someextent, can be solved by an exhaustive reordering andmatching within a local angular window.In our matching algorithm, the adaptation is achievedby adjusting the bounding box (Fig. 11) when an inexactmatch is found during the matching process. It can berepresented as follows:310IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 19, NO. 4, APRIL 1997=-+-RS|T|RS|T|w m nrrem nrrm nm nem nmPnQlmPnQhlh,afafejafafafabg qddqeDDDDWifotherwise?(19)DDDDDrerrem nrrm nm nem naamPnQlmPnQhlhFHGIKJ=-FHGIKJ-RS|T|RS|T|ifotherwiseddqe,afejafafaf?0(20)ddhllamnm nr+=+11,afafD(21)ddhhhamnm nr+=+11,afafD(22)?llamnm ne+=+11,afafhD(23)?hhamnm ne+=+11,afafhD(24)where w(m, n) represents the penalty for matching a pair ofminutiaeremPmPmPT,qej and renQnQnQT,qej, dl(m, n), dh(m, n),?l(m, n), and ?h(m, n) specify the adaptive bounding box inthe polar coordinate system (radius and radial angle); and his the learning rate. This elastic string matching algorithmhas a number of parameters which are critical to its per-formance. We have empirically determined the values ofthese parameters as follows: dl(0, 0) = 8; dh(0, 0) = +8;?l(0, 0) = 7.5;?h(0, 0) = +7.5; e = 30; a = 1.0; b = 2.0; g = 0.1;W = 200(a + b + g); h = 0.5. The values of dl(0, 0), dh(0, 0),?l(0, 0), and ?h(0, 0) depend on the resolution of fingerprintimages. Fig. 12 shows the results of applying the matchingalgorithm to an input minutia set and a template.Fig. 11. Bounding box and its adjustment. (a) (b) (c) (d)Fig. 12. Results of applying the matching algorithm to an input minutiaset and a template. (a) Input minutia set. (b) Template minutia set.(c) Alignment result based on the minutiae marked with green circles.(d) Matching result where template minutiae and their correspon-dences are connected by green lines.4EXPERIMENTALRESULTSWe have tested our on-line fingerprint verification systemon two sets of fingerprint images captured with two differ-ent inkless fingerprint scanners. Set 1 contains 10 imagesper finger from 18 individuals for a total of 180 fingerprintimages, which were captured with a scanner manufacturedby Identix. The size of these images is 380 380. Set 2 con-tains 10 images per finger from 61 individuals for a total of610 fingerprint images, which were captured with a scannermanufactured by Digital Biometrics. The size of these im-ages is 640 480. When these fingerprint images were cap-JAIN ET AL.: ON-LINE FINGERPRINT VERIFICATION311tured, no restrictions on the position and orientation of fin-gers were imposed. The captured fingerprint images varyin quality. Figs. 13 and 14 show some of the fingerprint im-ages in our database. Approximately 90 percent of the fin-gerprint images in our database are of reasonable qualitysimilar to those shown in Figs. 13 and 14, while about10 percent of the fingerprint images in our database are notof good quality (Fig. 15), which are mainly due to largecreases and smudges in ridges and dryness of the im-pressed finger. First, we report some initial results on fin-gerprint matching, followed by fingerprint verification. Thereasons why we did not use NIST-9 fingerprint database25 to test the performance of our system are as follows:1) we concentrate on live-scan verification, and2) NIST-9 fingerprint database is a very difficult finger-print database which contains a large number of fin-gerprint images of poor quality and no result hasbeen reported from other on-line verification systemsfor comparison.Fig. 13. Fingerprint images captured with a scanner manufactured byIdentix; the size of these images is 380 380; all the three images arefrom the same individuals finger.Fig. 14. Fingerprint images captured with a scanner manufactured byDigital Biometrics; the size of these images is 640 480; all the threeimages are from the same individuals finger.Fig. 15. Fingerprint images of poor quality.4.1 MatchingEach fingerprint in the test set was matched with the otherfingerprints in the set. A matching was labeled correct if thematched fingerprint was among the nine other fingerprintsof the same individual, and incorrect otherwise. A total of32,220 (180 179) matchings have been performed on testSet 1 and 371,490 (610 609) matchings on test Set 2. Thedistributions of correct and incorrect matching scores areshown in Fig. 16. It can be seen from this figure that thereexist two peaks in the distribution of matching scores. Onepronounced peak corresponds to the incorrect matchingscores which is located at a value around 10, and the otherpeak which resides at a value of 40 is associated with thecorrect matching scores. This indicates that our algorithm iscapable of differentiating fingerprints at a high correct rateby setting an appropriate value of the threshold. Table 1shows the verification rates and reject rates with differentthreshold values. The reject rate is defined as the percent-age of correct fingerprints with their matching scores belowthe threshold value. As we have observed, both the incor-rect matches and the high reject rates are due to fingerprintimages with poor quality such as those shown in Fig. 15. Wecan improve these matching results by ensuring that the da-tabase does not contain such poor quality fingerprint images.(a) Identix(b) Digital BiometricsFig. 16. Distributions of correct and incorrect matching scores; verticalaxis represents distribution of matching scores in percentage. (a) Dis-tribution of matching scores on test set 1 (180 images). (b) Distributionof matching scores on test set 2 (610 images).312IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 19, NO. 4, APRIL 19974.2VerificationIn on-line verification, a user indicates his/her identity.Therefore, the system matches the input fingerprint imageonly to his/her stored templates. To determine the verifica-tion accuracy of our system, we used each one of our data-base images as an input fingerprint which needs to be veri-fied. An input fingerprint image was matched against allthe nine other images of the same finger. If more than onehalf of the nine matching scores exceeded the thresholdvalue of 25, then the input fingerprint image is said to befrom the same finger as the templates and a valid verifica-tion is established. With this scheme, a 100 percent verifica-tion rate can be achieved with a reject rate around16 percent on both test sets. Again, this reject rate can bereduced by preprocessing the database to remove thestored templates of poor quality. This demonstrates that, inpractice, using a k-nearest neighbor type of matching is ade-quate for a successful verification. Table 2 shows the match-ing rate which is defined as the percentage of the correct fin-gerprints (of the same finger) present among the best n (n = 1,., 9) matches.For an on-line fingerprint verification system to be ac-ceptable in practice, its response time needs to be within afew seconds. Table 3 shows the CPU requirements of oursystem. The CPU time for one verification, including fin-gerprint image acquisition, minutia extraction and minutiamatching, is, on an average, approximately eight secondson a SPARC 20 workstation. It indicates that our on-linefingerprint verification system does meet the response timerequirement of on-line verification.The number of tests done on an automatic fingerprintidentification system is never enough. Performance meas-ures are as much a function of the algorithm as they are afunction of the database used for testing. The biometricscommunity is slow at establishing benchmarks and the ul-timate performance numbers of a fingerprint verificationsystem are those which you find in a deployed system.Therefore, one can carry out only a limited amount of test-ing in a laboratory environment to show the anticipatedsystem performance. Even in field testing, real performancenumbers are not importantits often the perceived per-formance which is crucial.5CONCLUSIONSWe have designed and implemented an on-line fingerprintverification system which operates in two stages: minutiaextraction and minutia matching. A modified version of theminutia extraction algorithm proposed in 18 is used in oursystem which is much faster and more reliable. A new hier-archical orientation field estimation algorithm results in asmoother orientation field which greatly improves the per-formance of the minutia extraction. An alignment-basedelastic matching algorithm is proposed for minutia match-ing. This algorithm is quite fast, because it is capable ofTABLE 1THEVERIFICATIONRATES AND REJECTRATESONTESTSETSWITHDIFFERENTTHRESHOLDVALUESThresholdValueVerificationRateRejectRateThresholdValueVerificationRateRejectRate2099.839 %11.23 %2099.426 %11.23 %2299.947 %13.33 %2299.863 %14.55 %2499.984 %16.48 %2499.899 %16.78 %2699.994 %20.49 %2699.969 %20.20 %2899.996 %25.19 %2899.989 %23.15 %30100 %27.72 %3099.999 %27.45 %(a) Using Identix system (180 images). (b) Using Digital Biometrics system (610 images).TABLE 2MATCHINGRATES ON TESTSETSUSINGTHELEAVE-ONE-OUTMETHODNumber ofBest MatchesMatching RateNumber ofBest MatchesMatching Rate191.17 %192.13 %294.72 %294.40 %396.89 %397.06 %498.17 %497.67 %598.89 %598.44 %699.39 %699.11 %799.72 %799.70 %899.83 %899.79 %999.94 %999.91%(a) Using Identix system (180 images). (b) Using Digital Biometrics System (610 images).TABLE 3AVERAGECPU TIME FOR MINUTIAEXTRACTIONANDMATCHING ON A SPARC 20 WORKSTATIONMinutia Extraction(seconds)Minutia Matching(seconds)Total(seconds)5.352.557.90JAIN ET AL.: ON-LINE FINGERPRINT VERIFICATION313finding the correspondences between minutia points with-out resorting to an exhaustive search. At the same time, thismatching algorithm has a good performance, because it hasthe ability to adaptively compensate for the nonlinear de-formations and inexact pose transformations between dif-ferent fingerprints. Experimental results show that oursystem achieves excellent performance in a realistic oper-ating environment. It also meets the response time re-quirement of on-line verification.Based on the experimental results, we observe that thematching errors in our system mainly result from incorrectminutiae extraction and inaccurate alignment. We observethat a number of factors are detrimental to the correct loca-tion of minutia. Among them, poor image quality is themost serious one. Therefore, in the future, our efforts willbe focused on global image enhancement schemes. Anotherissue related to minutia detection is to incorporate a struc-tural-based model in minutia detection which extracts mi-nutiae based on their local ridge formations. For elasticmatching, an important aspect is to utilize additional in-formation (e.g., neighboring ridges) about a minutia to in-crease the accuracy of alignment.ACKNOWLEDGMENTSWe gratefully acknowledge our useful discussions withNalina Ratha and Shaoyun Chen, and we would like tothank Nalina Ratha and Chitra Dorai for their careful com-ments on earlier versions of this paper.REFERENCES1 N. Ansari, M.H. Chen, and E.S.H. Hou, “A Genetic Algorithm forPoint Pattern Matching,” Chapt. 13, B. Soucek and the IRISGroup, eds., Dynamic, Genetic, and Chaotic Programming. NewYork: John Wiley & Sons, 1992.2 P.E. Danielsson and Q.Z. Ye, “Rotation-Invariant Operators Ap-plied to Enhancement of Fingerprints,” Proc. Eighth ICPR, pp. 329-333, Rome, 1988.3 Federal Bureau of Investigation, The Science of Fingerprints: Classi-fication and Uses. Washington, D.C.: U.S. Government Printing Of-fice, 1984.4 T.H. Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to Algo-rithms. New York: McGraw-Hill, 1990.5 D.C.D. Hung, “Enhancement and Feature Purification of Finger-print Images,” Pattern Recognition, vol. 26, no. 11, pp. 1,661-1,671,1993.6 S. Gold and A. Rangarajan, “A Graduated Assignment Algorithmfor Graph Matching,” Research Report YALEU/DCS/RR-1062,Yale Univ., Dept. of Computer Science, 1995.7 L. OGorman and J.V. Nickerson, “An Approach to FingerprintFilter Design,” Pattern Recognition, vol. 22, no. 1, pp. 29-38, 1989.8 K. Karu and A.K. Jain, “Fingerprint Registration,” Research Re-port, Michigan State Univ., Dept. of Computer Science, 1995.9 K. Karu and A.K. Jain, “Fingerprint Classification,” Pattern Recog-nition, vol. 29, no. 3, pp. 389-404, 1996.10 M. Kawagoe and A. Tojo, “Fingerprint Pattern Classification,”Pattern Recognition, vol. 17, no. 3, pp. 295-303, 1984.11 H.C. Lee and R.E. Gaensslen, eds., Advances in Fingerprint Technol-ogy. New York: Elsevier, 1991.12 D.P. Huttenlocher and S. Ullman, “Object Recognition UsingAlignment,” Proc. First Intl Conf. Computer Vision, pp. 102-111,London, 1987.13 Z.R. Li and D.P. Zhang, “A Fingerprint Recognition System WithMicro-Computer,” Proc. Sixth ICPR, pp. 939-941, Montreal, 1984.14 L. Coetzee and E.C. Botha, “Fingerprint Recognition in LowQuality Images,” Pattern Recognition, vol. 26, no. 10, pp. 1,441-1,460, 1993.15 B. Miller, “Vital Signs of Identity,” IEEE Spectrum, vol. 31, no. 2,pp. 22-30, 1994.16 A. Ranade and A Rosenfeld, “Point Pattern Matching by Relaxa-tion,” Pattern Recognition, vol. 12, no. 2, pp. 269-275, 1993.17 A.R. Rao, A Taxonomy for Texture Description and Identification.New York: Spr
- 温馨提示:
1: 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
人人文库网所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
|
2:不支持迅雷下载,请使用浏览器下载
3:不支持QQ浏览器下载,请用其他浏览器
4:下载后的文档和图纸-无水印
5:文档经过压缩，下载后原文更清晰
|
川公网安备: 51019002004831号