CN101925914B - Mark based on bioassay - Google Patents

Abstract

A biometric template matching method, comprising the steps of: providing (200, 201) a reference biometric template and a candidate biometric template, each template including position data and orientation data of a respective plurality of details; The orientation data for each minutiae is compared (212) with the orientation data for each minutiae from the reference template; when the orientation data for the selected pair do not differ by more than a first threshold, determining (213) the position data representing the selected pair of minutiae Poor displacement vectors; determine (214) the maximum number of displacement vectors that differ from each other by less than a second threshold; if the maximum number of displacement vectors is less than a third threshold (215), return a mismatch (216), otherwise return a match (217). A biometric based identification method, device and system, as well as a portable data carrier and a secure electronic system with a processor are also provided.

Description

Biometric based identification

In general, the present invention relates to the field of biometric-based identification, and in particular, to a biometric template matching method, a biometric-based identification method, device and system, as well as a portable data carrier and a secure electronic system with a processor.

For example, in order to ensure safe access to sensitive data or applications in computers and computer networks, to ensure safe access to restricted areas, to protect the security of transactions, to digitally sign electronic documents, etc., when allowing or denying access to protected environments Before, there was a growing need to uniquely identify a person.

Identification through the use of biometrics (“what are you”), that is, using physical or behavioral characteristics that are permanent and unique to each individual, has become more popular ”) or passwords (“what do you know”) are more resistant to fraudulent attempts. Biometric characteristics include, for example, fingerprints, irises or retinas, hand or facial geometry, voice, signature, handwriting, and typing habits.

The following discussion will be devoted to fingerprints. However, it should be understood that the basic principles of the invention can also be applied to other biometric features, in particular geometric features such as iris, retina, hand and facial geometry.

For identification using fingerprints, a reference image of a person's fingerprint is initially taken and a so-called enrollment template of several representative features (called minutiae) of it is stored for later comparison with the The so-called candidate templates of the fingerprints are compared or matched.

To increase security against enrollment templates being copied for misappropriation, instead of maintaining a central database of fingerprints of enrolled users from a protected environment, enrollment templates may be stored in portable data carriers.

As such, the user to be identified needs to present the portable data carrier together with his/her finger to the identification device, thus enabling two-factor identification.

In "Match-On-Card" biometric-based identification systems, the comparison between enrollment and candidate templates is performed by the portable data carrier itself in the form of a smart card with a microprocessor of. This further increases the resistance of the identification system, as no smart card is required to release the enrollment template.

WO 03/007125 discloses a device for securely communicating with a server, comprising a biometric sensor, a processor, and a smart card including matching logic and containing stored biometric data and encryption keys such as encryption keys. Secure data storage module for sensitive data. The biometric sample from the sensor is compared to the stored biometric data via the smart card matching logic. If they match, the processor approves the sensitive data from the smart card and communicates with the server using that sensitive data. WO03/007125 generally relies on known matching methods such as statistical methods, piecewise linear classifiers, and rule-based methods.

Biometrics are complex and thus represented by large electronic representations (images, voice signals, etc.), and while preserving the uniqueness of the biometrics themselves, their detection is subject to variation and error. For example, in the case of fingerprints, the same user's finger is almost never pressed to the exact same location on the biometric detector. Therefore, two biometric templates acquired by two detections of the same user's finger may not contain the same minutiae, and minutiae present in the two templates may be in different positions and orientations. Known matching methods typically involve rotation and translation of one template relative to the other, attempting to superimpose the two templates as if they were taken from the finger at the same location. Such a calibration step is followed by a comparison of the minutiae pairs from the two templates. Biometric template matching thus typically requires substantial memory and computing resources to perform the calibration steps.

M. Osborne and N.K. Ratha in "A JC-BioAPI Compliant: Smart Card with Biometrics for Secure Access Control", (J.Kittler and M.S. Nixon (Eds.): AVBPA 2203, LNCS 2688, pp.903-910, 2003) A fingerprint-based "match on card" application is disclosed. It is recognized in this literature that matching algorithms running on smart cards face significant constraints due to the limited resources of the smart card, especially the unavailability of floating-point co-processors. Therefore, the matching algorithm should only use a limited amount of dynamic memory and as few computation cycles as possible, and the biometric feature extraction should be performed outside of the smart card. According to this document, the JavaCard-BioAPI standard developed by the Java Card Forum allows secure registration of a reference biometric on a card and then performs candidate biometric verification without exposing the reference data outside the card. The actual matching algorithm is left to independent development in the industry.

Y.Gil et al. in "Fingerprint Verification System Involving Smart Card" (P.J.Lee and C.H.Lim (Eds.): ICISC 2002, LNCS 2587, pp.510-524, 2003, ) disclose a method using multi-resolution accumulation A "matching-on-card" system of processor arrays designed to meet the processing power and memory space specifications of smart cards. The system in this document involves, in the verification phase: an image preprocessing step, in which the fingerprint image is thinned to prevent distortion of the image acquired from the sensor; a minutiae extraction step, in which a template file is created , including the position, orientation and type of some minutiae; and a minutiae matching step, in which the input fingerprint is compared with the registered fingerprints. The minutiae matching step consists of a calibration phase, in which transformations such as translation and rotation between two fingerprints are estimated, and the two minutiae are aligned according to the estimated parameters; position, orientation, and type, compare them, and calculate a match score. In the calibration phase, a discretized transformation is established, including rotation and translation from each minutiae of the input fingerprint image to each minutiae of the registered fingerprint image, and the number of occurrences of each transformation is counted. In order to reduce the memory space requirement of the algorithm to allow implementation in a smart card, the document proposes to repeat this calibration phase from a coarser to a finer resolution of the transform space, centered on the most cumulative transform of the previous iterations. This comes at the cost of a larger number of instructions being executed, i.e., a longer execution time. In addition, the search for the transformation requires trigonometric functions that are not available in standard smart cards.

The technical problem underlying the present invention is to provide a matching method that can operate in a resource-constrained environment such as a smart card in order to achieve an efficient "matching on card" biometric based identification system and method.

Applicants have realized that the above problems can be solved by reducing the mutual rotation required for two biometric templates to be considered a match. In other words, during identification, a constraint is imposed on the degree the user is allowed to rotate the position of a biometric such as his/her finger relative to the position of the user's finger at the time of enrollment.

In a first aspect, the present invention relates to a method for template matching of biological assays comprising the steps of:

- providing a reference biometric template and a candidate biometric template, each template including position data and orientation data of respective multiple details,

- comparing the orientation data for each minutiae from the candidate bioassay template with the orientation data for each minutiae from the reference bioassay template;

- determining a displacement vector representing the difference of the position data of the selected pair of minutiae when the orientation data of each minutia from the candidate biometric template and each minutia from the reference biometric template differ by no more than a first threshold ,

- determining the maximum number of displacement vectors that differ from each other by less than a second threshold,

- comparing said maximum number of displacement vectors with a third threshold, and

- If said maximum number of displacement vectors is smaller than said third threshold, return no match, otherwise return match.

By first performing an orientation comparison between the minutiae, the need to rotate one template relative to another is advantageously avoided, and in particular, the need to use trigonometric functions is avoided.

In another of its aspects, the invention relates to a biometric-based identification method comprising an enrollment step comprising providing at least one reference biometric template of a user, and an identification step comprising the steps of:

- obtaining at least one candidate biometric template representing at least one biometric characteristic of the purported user,

- comparing the at least one reference template with the at least one candidate template,

- in case of a match, allow said purported user to access the protected environment, and

- in the case of a mismatch, deny said purported user access to the protected environment,

The comparing step includes the matching method above.

In another aspect, the invention relates to a portable data carrier having a processor comprising modules adapted to perform the steps of the matching method above.

In another aspect, the invention relates to a biometric based identification system comprising a biometric based identification device adapted to perform the steps of the above identification method and at least one portable data carrier provided with a processor.

In another aspect, the invention relates to a method of biometric-based identification comprising an enrollment step comprising storing at least one reference biometric template of a user in a portable data carrier having a processor, and an identification step comprising Include the following steps:

- electronically communicating said portable data carrier with a processor with a biometric based identification device,

- providing said portable data carrier with a processor with a candidate biometric template of the purported user,

- comparing a reference template with said candidate template in said portable data carrier with processor,

- in the case of a match, transferring at least one reference template from said portable data carrier with a processor to said biometric-based identification device, and, within said biometric-based identification device, comparing said at least a reference template and at least one candidate bioassay template,

- in case of a match, allow said purported user to access the protected environment, and

- In case of a mismatch, deny said claimed user access to the protected environment.

Further characteristics and advantages of the present invention will become clearer from the following detailed description of some preferred embodiments thereof, given as non-limiting examples only, with reference to the accompanying drawings, in which:

- Figure 1 shows a block diagram of a preferred embodiment of a biometric-based identification system according to the invention,

- Figure 2 shows a flow chart of a preferred embodiment of the biometric-based identification method according to the invention,

- Figure 3 shows a flow chart of a preferred embodiment of the matching method according to the invention,

- Figure 4 shows a flow chart of the steps of the matching method of Figure 3, and

- Figures 5 and 6 are exemplary illustrations of enrollment templates and candidate templates superimposed together.

In Fig. 1 a block diagram of a preferred embodiment of a biometric based identification system 1 according to the invention is shown.

The system 1 comprises a biometric based identification device 2 and at least one portable data carrier 3, 3', 3"... with a processor, such as a smart card of the microprocessor card type, eg SIM or USIM. For the sake of brevity , hereinafter, a portable data carrier 3 with a processor is often referred to as a smart card 3. The smart card 3 includes a memory 4 and a processor 5.

The biometric-based identification device 2 is part of, or is capable of electronically communicating with, the protected environment E to allow or deny the purported user's access to the protected environment E when identified by the biometric-based identification system 1 . Access to the protected environment E.

The protected environment E may be any of a variety of environments including, for example, sensitive data such as personal data or sensitive applications such as financial transactions, applications requiring electronic signatures of documents, such as for configuring computer Computers or computer networks for management applications or computer networks or communication base stations, electronic equipment such as mobile phones or similar products, automatic teller machines, restricted areas such as laboratories or banks, and similar areas.

The biometric based identification device 2 is able to communicate electronically with at least one smart card 3 via a smart card reader 6 and it comprises a memory 7 and a processor 8 .

Furthermore, the biometric-based identification device 2 also comprises at least one biometric detector 9, 9', 9"..., or is able to communicate electronically with them. In a simple embodiment, the biometric detector 9 is a fingerprint Sensors. Complementary biometric detectors 9', 9"..., if provided, can detect different biometric features.

The processor 8 of the biometric-based identification device 2 comprises at least one module 10, 10', 10"... adapted to drive a corresponding biometric detector 9, 9', 9"... in order to obtain a biometric The corresponding raw electronic representations 11 , 11 ′, 11 ″ . . . of the features are provided to the memory 7 of the recognition device 2 . Specifically, when the user's finger presses on the sensor 9, the original electronic image 11 of the fingerprint is acquired. The original electronic image 11 may advantageously be in any of a variety of standard image formats, such as BMP, JPG, GIF and similar formats.

When the fingerprint sensor 9 is a separate device from the biometric-based identification device 2 and has its own driver, the sensor driver module 10 may be a module AES4K from AuthenTec Corporation located in Melbourne, Florida, USA, and may, For example, the driver for the fingerprint sensor 9 communicates with the driver subsystem of Microsoft Windows ^™ .

The processor 8 of the biometric-based identification device 2 further comprises at least one module 12, 12', 12"... adapted to process a corresponding raw electronic representation 11, 11', 11"... and provide a corresponding Candidate biometric templates 13, 13', 13"... More specifically, the image processing module 12 is adapted to perform image enhancement or to supplement any image enhancement performed in the fingerprint sensor 9, such as for eliminating or filtering due to Such as acquisition errors or noise caused by ambient light, dust on the sensitive surface, unevenness of the sensitive surface, etc. The image processing module 12 is further adapted to extract the most important features from the fingerprint, such as fingerprint ridge bifurcation, concentration or interruption , called minutiae, and store candidate biometric templates 13 (this is a data structure comprising representative data for each minutiae) in the memory 7 of the recognition device 2 .

As described in further detail below, in a preferred embodiment of the present invention, more specifically, candidate templates 13 include positional data in the form of in-plane orthogonal coordinates x, y and in-plane angles with respect to the x-axis The orientation data exists in the form of t. The orientation data t represents the general orientation of the fingerprint ridge in the context of the minutiae, as specified by NIST - National Institute of Standards and Technology.

The image processing module 12 may use the detail extraction algorithm from NIST, and it may also include the module MinDetect, an open source program available at http://fingerprint.nist.gov/NFIS/index.html (at the filing date of this patent application).

The supplementary candidate templates 13', 13"..., if provided, may comprise the same type of data as the candidate template 13, or may comprise a different type of data representing details obtained from different biometrics of the user, such as iris, Retina, hand, face, and voice, signature, handwriting, and typing habits. For example, supplementary candidate templates 13', 13"... may include 3D position data of facial templates, or time and duration.

The memory 4 of the smart card 3 is adapted to securely store at least one reference or enrollment template 14, 14', 14", .... The enrollment template 14, 14', 14", ... is similar to the candidate template 13, 13' , 13″, ... Obtained at the initialization or registration step when the identity of the user is identified by the institution supervising the protected environment E.

The enrollment templates 14, 14', 14", ... comprise the same type of data and data structures as the candidate templates 13, 13', 13", .... More specifically, the registration template 14 includes position data in the form of in-plane orthogonal coordinates x, y and orientation data t in the form of (quantified) in-plane angles with respect to the X-axis.

The biometric based identification system 1 comprises a matching module 15 . For reasons that will become clearer below, the matching module 15 preferably comprises a coarser matching module 16 within the processor 5 of the smart card 3 and a finer matching module 17 within the processor 8 of the identification device 2 .

The matching module 15 , in particular the coarser matching module 16 of the smart card 3 , is adapted to compare the candidate template 13 with the enrollment template 14 . The matching module 15, in particular the finer matching module 17 in the recognition device 2, is also adapted to compare the complementary candidate templates 13', 13", ... with the complementary enrollment templates 14', 14", .. ., and/or more finely compare the candidate template 13 with the enrollment template 14.

As described more clearly below, when the finer matching module 17 is provided within the identification device 2, it may only approve storage in the memory 4 of the smart card 3 after the coarser matching module 16 of the smart card 3 returns a match. Registration templates 14, 14', 14", ....

Also for this purpose, the processor 8 of the biometric-based identification device 2 and the processor 5 of the smart card 3 each comprise a secure channel sub-module 18, 19 cooperating with each other to establish a secure communication channel between the identification device 2 and the smart card 3 20.

The secure communication channel 20 implements encryption to encrypt data exchanged between the identification device 2 and the smart card 3 and to ensure that each communication session between the identification device 2 and the smart card 3 is unique. The data exchanged includes matches or non-matches determined by the coarser matching module 16 of the smart card 3, and may include enrollment templates 14, 14', 14", ..., and any other data stored in the memory 4 of the smart card 3 Sensitive data 21 such as user personal data, digital certificates, user loyalty controlling access to the protected environment E, and similar data.

The secure channel submodule 18 of the identification device 2 can implement Microsoft Cryptography ServiceProvider, and the secure channel submodule 19 of the smart card 3 can implement Java Cryptography Extension. They can cooperate with each other by using PKCS - Public Key Cryptography Standard.

In a preferred embodiment, the secure communication channel 20 includes an asymmetric key encryption submodule 22, preferably using the RSA standard, and a symmetric key encryption submodule 23, preferably using the DES-Data Encryption Standard.

The asymmetric key encryption or RSA submodule is used to securely exchange the symmetric key 24 of the symmetric key encryption or DES submodule 23 .

In turn, the symmetric key encryption or DES submodule 23 is used to securely exchange data between the identification device 2 and the smart card 3 .

More specifically, the secure communication channel 20 includes a key container 25, which may be a key container as described by Microsoft Windows' CSP-Cryptographic Service Provider, or any other generally based on the Unix PKCS°11 standard components.

The key container 25 is adapted to store the session key 24 (which is the symmetric key 24 of the DES submodule 23), the private key 26 and the public key 27 of the identification device 2 and possibly the private key 28 and the public key 29 of the smart card 3 (They are the asymmetric keys of the RSA submodule 22).

Finally, the processor 8 of the biometric-based identification device 2 comprises a high-level module 30 suitable for interfacing with the protected environment E and with the smart card 3 and coordinating the various modules of the processor 8 described above.

Preferably, the high-level module 30 of the identification device 2 is implemented as a dynamic library Win32.

Similarly, the processor 5 of the smart card 3 includes a high-level module 31 adapted to interface with the biometric-based identification device 2, coordinate the various modules of the processor 5 described above, and lock/unlock itself file system and memory 4 access.

Preferably, the high level module 31 of the smart card 3 is implemented as a Java Card Applet of Java Card OS and provides a plurality of APDUs - Application Protocol Data Units - for interfacing with the biometric based identification device 2 .

The biometric-based identification system 1 described above is particularly suitable for carrying out the biometric-based identification method according to the invention, a preferred embodiment of which will be described below with reference to FIG. 2 .

In a registration step 100, one or more biometric reference or registration templates 14, 14', 14", ... are obtained (step 101) from a user whose identity is identified by the agency managing the protected environment E, and are stored In the memory 4 of the smart card 3 (step 102). The smart card 3 is handed over to the user (step 103).

The step 101 of obtaining an enrollment template is not fully described here, and this step 101 can be performed in many known ways. In any case, reference may be made to similar steps 110-113 of the identification step 104 described below.

The registration step 100 is performed only once for each user/smart card 3 .

After the registration step 100, whenever the purported user is to be identified, an identification step 104 is performed in order to allow (step 105) or deny (step 106) his/her access to the protected environment E. The identifying step 104 will be described in detail below.

In an initialization step 107, a portable data carrier with a processor or a smart card 3 storing templates 14, 14', 14", ... is electronically communicated with the biometric based identification device 2, i.e. the user sends The reader 6 presents the smart card 3 establishing a biometric based identification system 1 (step 108); and the identification system 1 establishes a secure communication channel 20 (step 109).

The step 109 of establishing a secure communication channel 20 is not mandatory, however, it should be done if preferred, since a session key 24, a private key 26 (28), and a public key are preferably generated in each session 27(29). In each session, the secure communication channel 20 initializes the key container 25 .

The secure channel sub-module 18 of the identification device 2 generates its private key 26 and its public key 27 and transmits the public key 27 to the secure channel sub-module 19 of the smart card 3 . The secure channel sub-module 19 of the smart card 3 generates a session key 24, encrypts the session key 24 with the identification device public key 27, and transmits the encrypted session key 24' to the secure channel sub-module 18 of the identification device 2. Finally, the secure channel sub-module 18 of the identification device 2 decrypts the session key 24 from the encrypted session key 24 ′ by using its private key 26 .

The secure channel submodule 19 of the smart card 3 can also generate its private key 28 and its public key 29 , and transmit the public key 29 to the secure channel submodule 18 of the identification device 2 .

In a biometric detection step 110 at least one biometric characteristic of the purported user of the protected environment E is detected by the biometric detectors 9, 9', 9", ... and the sensor driver modules 10, 10', 10". , and generate its 11, 11', 11", .... This step may include the purported user pressing his/her finger on the fingerprint sensor 9, speaking into a microphone or similar.

In a processing step 111, the raw electronic representations 11, 11', 11", ... are processed by processing modules 12, 12', 12", ... and at least one candidate template 13, 13', 13", . ... the processing step 111 may include an image enhancement step 112 and include a detail extraction step 113 .

Thereafter, the candidate template 13 is compared with the enrollment template 14 in a matching step 115 by the matching module 15, preferably using a matching or comparing method as will be discussed below.

Preferably, the matching step 115 is performed at least partly within the smart card 3 by its matching module 16 . Therefore, in such a case, the candidate template 13 is transmitted to the smart card 3 in the previous template communication step 114 , preferably via the secure communication channel 20 and encrypted with the session key 24 .

As a less preferred alternative, the enrollment template 14 is transmitted to the identification device 2, still via the secure communication channel 20, and it is encrypted with the session key 24, and the matching step 115 is performed within the identification device 2 by its matching module 17 performed. As yet another less preferred alternative, matching is performed by one of the smart card 3 or the identification device 2, directly accessing the memory of the other of the smart card 3 or the identification device 2, the template communication step 114 being omitted.

In the case of a match, access to the protected environment E may be allowed immediately (step 105). In case of a mismatch, access to the protected environment E may be denied immediately (step 106). Alternatively, in the case of a mismatch, the biometric feature detection step 110, the processing step 111, the template communication step 114 and the matching step 115 may be repeated, preferably no more than a selected number of times, e.g. by dividing the number of attempts with Thresholds are compared to those checked in step 116.

In case of a match, a step 117 of unlocking smart card functions and applications may be provided. Smart card applications may include digital signature applications, encryption applications, mobile communication applications, and the like.

More specifically, the functions and applications of the smart card 3 may include, for example, an authentication function conforming to standard 802.11, in particular, EAP-Extensible Authentication Protocol, such as EAP-Extensible Authentication Protocol when the protected environment E is a GSM or mobile communication network. SIM, or, such as EAP-TLS (Transport Layer Security) when the protected environment E is a computer or a computer network, and a smart card 3 for exchanging digital certificates, such as, for example, for securing e-mail messages, for Securing access to networks or computers or computer network applications; when the protected environment E is a restricted area, non-contact authentication applications based on RFID-Radio Frequency Identification, etc.

Access allowing step 105 may include transferring sensitive data 21 from smart card 3 to identification device 2 (step 118), preferably over secure channel 20, encrypting sensitive data 21 with session key 24, and transferring the sensitive data to 21 is forwarded from the identification device 2 to the protected environment E (step 119).

In a particularly preferred embodiment, the biometric-based identification method comprises two levels of comparison of biometric templates. Accordingly, the matching step 115 , which is preferably performed by the matching module 16 of the smart card 3 having more limited memory and computing resources, is the first or coarser matching step 115 .

In the case of a match in the first matching step 115, the granting access step 105 is not performed immediately accordingly. Instead, the unlocking step 117 is performed as a first or coarser unlocking step, wherein only a limited subset of data and applications are unlocked within the smart card 3 .

In the case of a match in the first or coarser matching step 115 , a second or finer matching step 121 is carried out by the matching module 17 of the recognition device 2 having relatively large memory and computing power. The fine matching step 121 may include a finer comparison between the same candidate template 13 and enrollment template 14 already used by the smart card 3 in the coarser matching step 115, or may also include supplementary enrollment templates 14', 14 One or more comparisons between pairs of " and candidate templates 13', 13"..., eg, templates of more complex biometric data such as iris data, voice data, etc.

In particular, in the case of a match as a result of the first or coarser matching step 115, the smart card 3 may only unlock access to its file system in a step 117, and thus the identification device 2 may approve the enrollment template 14 and/or Or supplementary enrollment templates 14', 14", ..., alternatively, a second template communication step 120 may be performed, wherein the enrollment templates 14 or supplementary enrollment templates 14', 14", ... are transmitted from the smart card 3 To the identification device 2, this preferably takes place over a secure communication channel 20, encrypted with a session key 24.

In case of a match as a result of the fine matching step 121, the step 105 of allowing access to the protected environment E is fully performed, i.e. steps 118 and 119 are performed, and in addition a second or fine unlocking step 122 may also be performed, in which , to unlock all data and applications on the smart card 3.

In case the result of fine matching step 121 is no match, step 123 of locking smart card 3 may be performed and access to protected environment E is immediately denied (step 106), or return to biometric feature detection step 110 for further processing. Further identification attempts are preferably not to exceed a selected number of times as checked at step 116 .

A preferred embodiment of a biometric template matching method for comparing a reference or enrollment biometric template 14 and a candidate biometric template 13 according to the present invention will now be described with reference to FIG. 3 .

Due to the limited memory and computing power required by the matching method, it is preferably used in the matching step 115 when implemented by the matching module 16 of the smart card 3, either as a first or coarser matching step or as a biometric based A single matching step for the identification method. However, the matching method can also be advantageously used by electronic devices with unlimited resources, including biometric-based identification devices 2 .

The matching method will be described below with reference to fingerprint recognition.

The matching method relies on providing a reference or enrollment biometric template 14 and a candidate biometric template 13 in steps 200 and 201 respectively, with a specific data structure.

As briefly mentioned above, the data structure of each template 13, 14 includes, for each of its details, positional data in the form of in-plane orthogonal coordinates, such as 2D Cartesian coordinates x, y, and Orientation data t in the form of an in-plane angle with respect to the X-axis.

More specifically, each bioassay template 13(14) may be an array of short types of size 3*M(3*N), where M(N) is the number of minutiae of the template 13(14), And where, for 0<=i<M(0<=i<N):

- item 3*i+0 is the abscissa x of the ith minutiae,

- item 3*i+1 is the ordinate y of the ith minutiae,

- Item 3*i+2 is the orientation angle t of the ith minutiae.

The position data coordinates x, y can be expressed in any length unit along the X, Y axis, the orientation data t is preferably quantized, i.e. the orientation data t is in units defined by a preselected ratio of a circle angle Angle u to represent. Preferably, the preselected ratio of the circumference angles is 1/32, ie 11.25°, as specified by the minutiae extraction algorithm from NIST.

Since during the extraction of minutiae from detected fingerprints (step 113 of the biometric-based identification method outlined above), the orientation of each minutiae is typically obtained from multiple pixels of the raw fingerprint image in the vicinity of the minutiae point, Using such a relatively large unit angle u narrows the error margin later on in determining whether two minutiae match in orientation. In fact, the same minutiae, and thus the same local orientation, will obtain the same quantized angle in both fingerprints, regardless of absolute orientation differences within angular units caused by different orientations of the finger relative to the biometric detector 9 .

Correspondingly, if the details of the candidate template 13 (enrolment template 14) are oriented in a direction forming an angle α with the X-axis, its orientation data t will be set in the quantization step 202 (203) as

in, Represents the integer part of .

Then, auxiliary data structures for use in the matching method described fully below are provided in an initialization step 204, more specifically, an empty 2D displacement array L is provided in a step 205, and the first threshold tlim, the second The second threshold Range and the third threshold Mlim.

The displacement array L may be an array of type short of size 2*D, where D is the number of displacement vectors between minutiae pairs from candidate templates 13 and enrollment templates 14 selected according to the similarity criterion described in detail below , where, for 0<=i<D:

- the term 2*i+0 is the displacement Δx along the abscissa x of the ith minutiae pair denoted by w below,

- The term 2*i+1 is the displacement Δy along the ordinate y of the ith minutiae pair denoted below by z.

The maximum size of the displacement array L is in principle M*N, however, it can be limited to, for example, 150 in order to speed up the execution of the matching method in a resource-constrained environment such as the processor 5 of the smart card 3 .

The first threshold tlim is the number of unit angle u, preferably set to 1. The second threshold Range is the length in the displacement vector space W, Z. The third threshold Mlim is a pure number Mlim<=M or Mlim<=min(M, N), where M is the number of minutiae of the enrollment template 14 and N is the number of minutiae of the candidate template 13 as described above. In particular, Mlim may be chosen as a percentage of the number M of details of the enrollment template 14 .

In step 207, the displacement array L is filled.

In the outer loop comprising M iterations, a minutiae from the enrollment template 14 is selected (step 209) as illustrated by step 208 of comparing pointers to M, while in the inner loop comprising N iterations, as A minutiae from the candidate template 13 is selected (step 211) as illustrated by the step 210 of comparing pointers to M.

For each pair of minutiae m(xm, ym, tm), n(xn, yn, tn) selected in steps 209 and 211, an orientation data comparison (step 212) is performed, wherein the orientation data tm of the two minutiae are checked , whether the tn difference does not exceed the first threshold tlim, that is, whether

|tm-tn|<=tlim (2)

Among them, |.| represents the absolute value of .

It should be noted that using the threshold tlim in the orientation data comparison is advantageous because the unit angle u of the orientation data used to quantify the details of the enrollment template 14 and the candidate template 13 is relatively large. In practice, nearly equal angles, such as angles differing by only one degree, may be rounded to different angles expressed by the chosen unit angle u by equation (1) above. Once the comparison of step 212 is performed as an equality check, the two details will be considered different.

As an example, two minutiae towards 112° and 113° respectively would be represented in the biometric template 14, 13 by the following angles:

When the result of the towards data comparison step 212 is affirmative, in step 213 the displacement vector V(w, z) is appended to the displacement array L, where

w=xm-xn (5)

z=ym-yn (6)

A pseudocode of an implementation of step 207 of filling displacement array L will be given below:

for each minutia m(xm, ym, tm) of enrollment template 14

for each minutia n(xn, yn, tn) of candidate template 13

if|tm-tn|<=tlim

calculate V(xm-xn, ym-yn)

append V to L

The significance of the above steps and the steps to be described in the matching method can be better understood with reference to FIGS. 5 and 6 .

In these figures, the M=8 minutiae m1 to m8 of the enrollment template 14 are represented by solid shapes, while the N=8 minutiae n1 to n8 from the candidate template 13 are represented by hollow shapes. However, it should be noted that the number M, N of minutiae in the two templates is not always equal.

Displacement vectors V1 to V14 and V21 to V35 between similar pairs of minutiae, as evaluated in the minutiae orientation comparison step 212, are shown in solid and dashed lines for greater clarity. These displacement vectors V are appended to the displacement array L in step 213 . Conversely, displacement vectors between non-similar pairs of minutiae, the exemplary vector V' shown by the dotted line between minutiae n7 and m8 in Figure 5, are neither calculated nor appended to the displacement array L.

Thus, although in principle there are M*N displacement vectors between minutiae pairs from the two templates 13, 14, the matching method of the invention reduces the considered displacement vectors by first performing the minutiae orientation data comparison step 212 quantity.

For ease of illustration, the two templates 13, 14 of Figures 5 and 6 are exact matching templates, ie they include exactly the same details. In FIG. 5 , the candidate template 13 is only moved relative to the registration template 14 , while in FIG. 6 , the candidate template 13 is only rotated around the center C relative to the same registration template 14 .

The displacement vectors V1 to V8 and V21 to V28 between the actual corresponding detail pairs n1, m1; n2, m2; ... n8, m8 from the two templates 13, 14 are shown in solid lines, while the displacement vectors V9 to V14 and V29 to V35 are shown in dashed lines.

It will be seen that in FIG. 5 the displacement vectors V1 to V8 have the same length and orientation, whereas in reality each of them represents the actual translation of the enrollment template 14 to the candidate template 13 . On the other hand, vectors V9 to V14 differ in length and/or orientation because they are derived from minutiae pairs n1,m6; n2,m4; n4,m2; n5,m7;n6 that happen to have the same or similar orientation. , m1; n7, m5 generated.

It is easy to understand that, in principle, when the finger has only translation during the detection of the candidate template relative to the position it had at the time of registration, if M and N are not equal because a part of the finger is outside the range of the biometric detector 9, then the same The number of displacement vectors will correspond to the minimum of M and N. On the other hand, the number of pseudo-displacement vectors, such as vectors V9 to V14, will statistically be smaller, and any subset of the same pseudo-vectors will include fewer vectors.

Under real-life conditions, even considering a pure translation of the two templates, due to the computation performed to extract minutiae from the detected fingerprint (step 113 of the biometric-based identification method outlined above), from the two templates 13, 14 Actual Corresponding Details The solid-line displacement vectors V1 to V8 between pairs n1, m1; n2, m2; ... n8, m8 are actually slightly different in length and/or orientation.

Furthermore, in the case of rotation between the templates 13, 14 (Fig. 6), although between the actual corresponding minutiae pairs n1, m1; n2, m2; ... n8, m8 from the two templates 13, 14 Between, the solid-line displacement vectors V21 to V28 are also different in length and orientation. Specifically, they will be chords of a circle centered on the center of rotation C and pass through the pair of minutiae. Furthermore, compared to the pseudo-displacement vector V29 between the minutiae pairs n1, m6; n2, m4; n4, m8; n5, m7; n6, m1; n7, m5; n8, m3 that happen to have the same or similar orientation A subset of the V35, they are more similar in length - and less critical in orientation.

Also, in principle, if M and N are not equal because part of the finger is out of range of the biometric detector when the finger is only rotated during the detection of the candidate template relative to the position it had when the enrollment template was detected, then There will be several displacement vectors of similar length and orientation corresponding to the minimum of M and N, while the number of pseudo displacement vectors such as vectors V29 to V35 will be statistically less, while the same pseudo Any subset of vectors will include fewer vectors.

Under real life conditions, the candidate template 13 will both translate and rotate relative to the enrollment template 14 . It should be understood that the above principle still holds true, that in the case where two templates 13, 14 come from the same user's finger, there will be several displacement vectors between the actual corresponding minutiae pairs that differ only slightly in length and orientation , which is larger than the subset of pseudo-displacement vectors and comparable to the minimum values of M and N. Also, it is easy to understand that where the two templates 13, 14 do not come from the same user's fingers, the difference between the displacement vectors will be very large, i.e. the number of displacement vectors that differ only slightly in length and orientation will be comparable Low.

Based on the above considerations, the matching method includes, after the steps outlined above, obtaining the step 214 of the maximum number Score of the displacement vector V that differs no more than the second threshold Range (described in more detail below), and Step 215 of comparing the maximum number Score with the third threshold Mlim.

In case the maximum number Score is equal to or greater than the third threshold Mlim, a match is returned in step 216 , and in case the maximum number Score is lower than the third threshold Mlim, a mismatch is returned in step 217 .

It should be noted that the threshold Range, which represents how similar the two displacement vectors Vr and Vs should be in terms of length and orientation, should in principle be a two-dimensional threshold. In fact, the difference of the vectors is the vector ΔV itself. However, the orientation of the difference vector ΔV is not of concern since it is the relative orientation of the two displacement vectors that matters, not their absolute orientation. As such, the threshold Range only needs to be equal to the threshold involving the length or size of the vector.

Due to the choice of the data structure representing the displacement array V, where each displacement vector is represented in the space W, Z by the above equations (5) and (6), the threshold Range can be expressed as a single graph representing the difference vector ΔV Limits for each coordinate W, Z. The geometric meaning of such a displacement vector similarity criterion stipulates that the difference vector ΔV is inscribed in a square with side Range.

Two displacement vectors Vr (wr, zr), Vs (ws, zs) will differ accordingly and do not exceed the second threshold Range, if

Δw=|wr-ws|=|(xmi-xnj)-(xmk-xml)|<=Range (7)

Δz=|zr-zs|=|(xmi-xnj)-(xmk-xml)|<=Range (8)

If a different data structure is used to represent the displacement vector V, such as polar coordinates ρ, θ, then the threshold Range will be represented as a single graph representing the limits of the radius coordinate ρ. The geometric meaning of such a displacement vector similarity criterion stipulates that the difference vector ΔV is inscribed in a circle with radius Range.

In the step 214 of acquiring the maximum number Score of displacement vectors V whose difference does not exceed the second threshold Range, the above formulas (7) and (8) can be used to compare each pair of two displacement vectors Vr, Vr, Vs, and count the number of successes, to execute.

More advantageously, step 214 is performed by the following steps.

First, in step 218, the displacement array L is sorted according to the coordinate W. Preferably, this is performed using the known insertion sort algorithm, which does not require any auxiliary arrays, since both array items are swapped simultaneously.

Then, by browsing the displacement array L, a first displacement subarray LW is generated (step 219), which is a relatively long subset of the items of the displacement array L whose W components differ by no more than the second Threshold Range. Note that the W-verified shift sub-array LW can be stored in the same memory location as the shift array L.

FIG. 4 shows the step 219 of generating the first or verified W-shifted sub-array LW in more detail. In an outer loop comprising a number of iterations equal to the number of entries D in the displacement array L minus 1, as shown in step 220 of comparing pointer r with D, an entry Lr(wr, zr) of the displacement array L is selected (step 221), and in an inner loop comprising D-r iterations, as shown in step 222 comparing pointer s to D-r, select the next entry Vs(ws, zs) of displacement array L (step 223). Equation (7) is then checked in step 224 and if the check is positive, the CurrentLength variable is incremented in step 225 . At the end of the inner loop, the Maximum Length variable is stored in step 226 as the maximum value of the previously stored CurrentLength and Maximum Length, and the Max_W_index is stored in step 227 as the current index r or the previously stored index Max_W_index respectively.

Note that to minimize execution time, the inner and outer loops can also end when the number of logarithms to be processed added to CurrentLength will not exceed Maximum Length.

At the end of the outer loop 220, the entry Lr(wr, zr) of r=Max_W_index in the displacement array L is selected and retained in the displacement subarray VW of the verified W (step 228). Then, browse through the displacement array L again. In a loop comprising an iteration number at most equal to D-r, the subsequent entry Vs(ws, zs) in the displacement array L is selected (step 230), as shown by step 229 comparing pointer s to D.

Then, in step 231, formula (7) is checked, and if the result of the check is affirmative, in step 232, the entry Vs(ws, zs) is kept in the verified W-shifted subarray VW. Return to Fig. 3, then, generate the second displacement subarray LWZ (step 233) by browsing through the displacement subarray LW of W verified, which is a relatively long subset of the items of the first displacement subarray LW, according to the above Formula (8), the difference between its Z components does not exceed the second threshold Range. Note that the second shifted sub-array LWZ may be stored in the same memory location as the shifted array V and the first shifted sub-array LW. Step 233 can be performed as step 219 described in detail above with necessary changes.

Then, in step 234 the number of items of the second shift sub-array LWZ is counted, and it is the maximum number Score to be used in the comparison step 215 .

It should be understood that the selection of the value of the threshold Range is critical to the execution of the matching method. If a value is chosen that is too large, displacement vectors between pairs of minutiae from enrollment templates 14 and candidate templates 13 that do not actually correspond will be considered similar and the rate of false matches will increase. Conversely, if the value chosen is too small, there will be a gap between the actual corresponding minutiae pairs from the enrolled template 14 and the candidate template 13 due to the translation and rotation of the finger during detection of the candidate template 13 relative to the position it had at the time of enrollment. The displacement vectors of will be considered dissimilar, and the ratio of false mismatches will be increased.

The matching method according to the invention can also be applied to candidate and enrollment templates 13, 14 comprising 3D position data, such as in the case where the biometric feature is the user's hand, face or iris.

Claims (20)

1. A biometric template matching method comprising the steps of:

-providing (200, 201) a reference biometric template (14) and a candidate biometric template (13), each template (14, 13) comprising position data (x, y) and orientation data (t) for a respective plurality of details (m, n),

-comparing (212) the orientation data (tn) of each detail (n) from the candidate biometric template (13) with the orientation data (tm) of each detail (m) from the reference biometric template (14),

the method is characterized in that:

-determining (213) a displacement vector (V (w, z)) representing the difference of the position data (x, y) of a selected pair of details (m, n) from the candidate biometric template (13) and a reference biometric template (14) when the orientation data (tm, tn) of the selected pair differ by no more than a first threshold value (tlim),

-determining (214) a maximum number (Score) of displacement vectors (V) differing from each other by less than a second threshold (Range),

-comparing (215) the maximum number (Score) of displacement vectors (V) with a third threshold (Mlim), and

-returning a mismatch (217) if the maximum number (Score) of displacement vectors (V) is smaller than the third threshold (Mlim), otherwise returning a match (216).

2. The method according to claim 1, wherein, in the step of providing a template (200, 201), the position data (x, y) comprises in-plane orthogonal coordinates.

3. The method according to claim 1 or 2, wherein, in the step of providing a template (200, 201), the orientation data (t) comprises an in-plane angle (t) with respect to a reference axis (X).

4. A method according to claim 3, wherein said in-plane angle (t) is expressed in units of angle (u) which is a preselected ratio of one circumference angle.

5. The method of claim 4, wherein the preselected ratio of the one peripheral angle is 1/32.

6. Method according to claim 4, wherein said first threshold value (tlim) is one angular unit (u).

7. A method according to claim 5, wherein said first threshold value (tlim) is one angular unit (u).

8. The method according to claim 1, wherein the third threshold (Mlim) is a function of the number of details (M) in the reference biometric template (14).

9. The method according to claim 7, wherein the third threshold (Mlim) is a percentage of the number of details (M) in the reference biometric template (14).

10. Method according to claim 1, wherein the displacement vectors (V (w, z)) are stored in a displacement array (L) and the step of determining (214) the maximum number (Score) of displacement vectors (V) that differ from each other by less than the second threshold (Range) is performed by:

-ordering (218) the displacement array (L) according to a first coordinate (w) of the displacement vector (V),

-generating (219) a first displacement sub-array (LW) being a subset of entries in a displacement array (L) whose first coordinates (w) differ by no more than the second threshold value (Range),

-generating (225) a second sub-array of shifts (LWZ), which is a subset of entries in the first sub-array of shifts (LW), whose second coordinates (z) differ by no more than the second threshold (Range), and

-counting (234) the number of terms in the second sub-array of shifts (LWZ).

11. A biometric-based identification method comprising an enrollment step (100), said enrollment step (100) comprising a step of providing (101) at least one reference biometric template (14, 14', 14 ") of a user, and an identification step (104), said identification step (104) comprising the steps of:

-obtaining (110, 111) at least one candidate biometric template (13, 13') representative of at least one biometric characteristic of the purported user,

-comparing (115, 121) the at least one reference template (13, 13 ') and the at least one candidate template (14, 14'),

-in case of a match, allowing (105) the purported user to access a protected environment (E), and

-in case of a mismatch, denying (106) the purported user access to a protected environment (E),

the method is characterized in that the comparing step (115, 121) comprises a matching method according to any of claims 1-10.

12. The method according to claim 11, wherein the comparing step (115) is at least partly performed by a portable data carrier (3) having a processor.

13. The method according to claim 12, further comprising, in case of a match, unlocking (117, 122) access to the portable data carrier with processor (3).

14. The method according to claim 13, wherein the comparison (115, 121) comprises a first comparison step (115) and at least one second comparison step (121), the first comparison step (115) being performed by a portable data carrier (3) having a processor and the at least one second comparison step (121) being performed by a biometric-based identification device (2).

15. The method according to claim 14, further comprising the step of transferring (120) at least one reference template (13, 13', 13 ") from the portable data carrier with processor (3) to the biometric-based identification device (2) in case of a match in the first comparing step (115).

16. Method according to claim 12, further comprising, in case of a mismatch, the step of locking (123) access to the portable data carrier (3).

17. The method according to claim 11, wherein the step of obtaining (110, 111) at least one candidate template (13, 13', 13 ") comprises a detail extraction step (113).

18. An apparatus for biometric template matching, comprising:

-means for providing (200, 201) a reference biometric template (14) and a candidate biometric template (13), each template (14, 13) comprising position data (x, y) and orientation data (t) of a respective plurality of details (m, n),

-means for comparing (212) the orientation data (tn) from each detail (n) of the candidate biometric template (13) with the orientation data (tm) from each detail (m) of the reference biometric template (14),

the apparatus is characterized by further comprising:

-means for determining (213) a displacement vector (V (w, z)) representing the difference of the position data (x, y) of a selected pair of details (m, n) from the candidate biometric template (13) and a reference biometric template (14) when the orientation data (tm, tn) of the selected pair differ by no more than a first threshold value (tlim),

-means for determining (214) a maximum number (Score) of displacement vectors (V) differing from each other by less than a second threshold (Range),

-means for comparing (215) said maximum number (Score) of displacement vectors (V) with a third threshold (Mlim), and

-means for returning a mismatch (217) if the maximum number (Score) of displacement vectors (V) is smaller than the third threshold (Mlim), otherwise returning a match (216).

19. A biometric-based identification system (1) comprising means for providing (101) at least one reference biometric template (14, 14', 14 ") of a user, and means for identifying (104), said means for identifying (104) comprising:

-means for obtaining (110, 111) at least one candidate biometric template (13, 13') representative of at least one biometric characteristic of the purported user,

-means for comparing (115, 121) said at least one reference template (13, 13 ') and said at least one candidate template (14, 14'),

-means for allowing (105) said purported user to access a protected environment (E) in case of a match, and

-means for denying (106) said purported user access to a protected environment (E) in case of a mismatch,

the system is characterized in that the means for comparing (115, 121) comprise an apparatus for biometric template matching according to claim 18.

20. A biometric-based identification method comprising an enrolment step (100), the enrolment step (100) comprising: -a step of storing (102) in a portable data carrier (3) having a processor at least one reference biometric template (14, 14', 14 ") of a user, and-a recognition step (104), said recognition step (104) comprising the steps of:

-electronically communicating (108) the portable data carrier with processor (3) with a biometric-based identification device (2),

-providing (110, 111, 114) the purported user's candidate biometric template (13) to the portable data carrier with processor (3),

-comparing (115) a reference template (14) and the candidate template (13) within the portable data carrier with processor (3),

-in case of a match, transmitting (120) at least one reference template (14, 14 ', 14 ") from the portable data carrier with processor (3) to the biometric-based identification device (2), and comparing (121) the at least one reference template (14, 14 ', 14") with at least one candidate biometric template (13, 13 ', 13 ") within the biometric-based identification device (2), wherein the step of comparing (121) the at least one reference template (14, 14 ', 14") with at least one candidate biometric template (13, 13 ', 13 ") comprises the method according to any one of claims 1-10,

-in case of a match, allowing (105) the purported user to access a protected environment (E), and

-in case of a mismatch, denying (106) the purported user access to the protected environment (E).