CN101925914B - Mark based on bioassay - Google Patents

Abstract

A kind of biometric template matching process, comprises the following steps: to provide (200,201) reference biometric template and candidate's biometric template, and each template includes the position data of respective multiple details and towards data；By each details from candidate template towards data with from reference template each details compare (212) towards data；When selected to towards data difference less than first threshold time, determine that (213) represent the displacement vector of the difference of the position data of selected details pair；Determine (214) the difference each other maximum quantity less than the displacement vector of Second Threshold；If the described maximum quantity of displacement vector is less than the 3rd threshold value (215), then returns and do not mate (216), otherwise return coupling (217).Additionally provide recognition methods based on bioassay, equipment and system, and there is portable data medium and the secure electronic systems of processor.

Description

Biometric-based identification

The present invention relates generally to the field of biometric-based identification, and more particularly to a biometric template matching method, a biometric-based identification method, device and system, as well as a portable data carrier with a processor and a secure electronic system.

There is an increasing need to uniquely identify a person before allowing or denying access to a protected environment, for example, to ensure secure access to computers and sensitive data or applications in computer networks, to ensure secure access to restricted areas, to protect the security of transactions, to digitally sign electronic documents, and so on.

Identification by using biometrics ("what you are"), i.e. using physical or behavioural features that are permanent and unique for each person, has become increasingly popular because it is more resistant to fraud attempts than identification by tokens ("what you have") or passwords like ("what you know"). Biometric features include, for example, fingerprints, iris or retina, hand or facial geometry, voice, signature, handwriting, and typing habits.

The following discussion will be specific to fingerprints. However, it should be understood that the underlying principles of the invention may also be applied to other biometric features, in particular geometric features such as iris, retina, hand and face geometries.

For identification with fingerprints, a reference image of a person's fingerprint is initially taken and several so-called enrollment templates of their representative features (called minutiae) are stored for later comparison or matching with so-called candidate templates from each detected fingerprint from the purported person.

To increase the security against theft of the enrolment template after it has been copied, the enrolment template may be stored in the portable data carrier instead of maintaining a central database of fingerprints of registered users from the protected environment.

Thus, the user to be identified needs to present the portable data carrier and his/her finger to the identification device in order to achieve two-factor identification.

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

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

Biometric features are complex and therefore represented by large electronic representations (images, speech signals, etc.), and their detection can be subject to variations and errors despite retaining the uniqueness of the biometric features themselves. For example, in the case of a fingerprint, the finger of the same user is almost never pressed at exactly the same location on the biometric detector. Thus, two biometric templates acquired for two detections of the same user's finger may not contain the same details, and the details present in the two templates may be different in position and orientation. Known matching methods then typically involve rotation and translation of one template relative to the other, in an attempt to superimpose the two templates as if they were taken from a finger at the same location. Such a calibration step is followed by comparing pairs of details from the two templates. Biometric template matching typically requires a large amount of memory and computational resources to perform the calibration step.

M.osborne and n.k.ratha in "a JC-bio api compant: smart Card with biometrics for Secure Access Control, "(J.Kittler and M.S.Nixon (Eds.): AVBPA 2203, LNCS 2688, pp.903-910, 2003) discloses a fingerprint-based" match on Card "application. It is recognized in this document that matching algorithms running on a smart card face significant constraints due to limited smart card resources, especially the unavailability of floating point coprocessors. 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 the smartcard. According to this document, the JavaCard-BioAPI standard developed by Java Card Forum (Java Card Forum) allows securely registering reference biometrics on a Card and then performing candidate biometric authentication without exposing the reference data outside the Card. The actual matching algorithm is left to be independently developed in the industry.

Y.gil et al in "Fingerprint Verification System inventing Smart Card" (p.j.lee and c.h.lim (Eds.): ICISC 2002, LNCS 2587, pp.510-524, 2003,) discloses an "on-Card matching" System using a multi-resolution accumulator array, which is designed to meet the processing power and memory space specifications of a Smart Card. The system in this document involves, in a verification phase: an image preprocessing step in which the fingerprint image is refined to prevent distortion of the image acquired from the sensor; a detail extraction step in which a template file is created, including the position, orientation and type of some details; and a minutiae matching step in which the input fingerprint is compared with the registered fingerprint. The minutiae matching step comprises a calibration phase in which the transformations, such as translation and rotation, between the two fingerprints are estimated, and the two minutiae are aligned according to the estimated parameters; and a matching stage in which the two details are compared based on their position, orientation and type and a matching score is calculated. In the calibration phase, a discretized transform is established, including a rotation and translation from each minutia of the input fingerprint image to each minutia of the enrolled fingerprint image, and the number of occurrences of each transform is counted. In order to reduce the memory space requirements of the algorithm to allow implementation in a smart card, the document proposes to repeat the calibration phase from a coarser resolution to a finer resolution of the transformation space, centred on the most cumulative transformation of the previous iteration. This is at the cost of a larger number of instructions being executed, i.e., longer execution time. Moreover, the search for transformations also 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 be run in a resource-constrained environment, such as a smart card, in order to achieve an efficient "match-on-card" biometric-based identification system and method.

The applicant has perceived that the above problem can be solved by reducing the mutual rotation that is required to make two biometric templates considered to match. In other words, during recognition, constraints are imposed on the degree to which 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 registration.

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

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

-comparing orientation data for each detail from the candidate biometric template with orientation data for each detail from the reference biometric template;

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

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

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

-returning a mismatch if the maximum number of displacement vectors is less than the third threshold, otherwise returning a match.

By first performing an orientation comparison between the details, the need to rotate one template relative to the other 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 a registration 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 feature of the purported user,

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

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

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

the comparing step includes the above matching method.

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

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 having a processor.

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

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

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

-comparing a reference template and the candidate template within the portable data carrier with a processor,

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

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

-in case of a mismatch, denying said purported 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 purely by way of non-limiting example 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,

FIG. 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,

FIG. 4 shows a flow chart of the steps of the matching method of FIG. 3, an

Fig. 5 and 6 are exemplary illustrations of the enrolled template and the candidate template 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, e.g. a SIM or USIM. For the sake of brevity, the portable data carrier 3 with the processor is often referred to below as a smart card 3. The smart card 3 comprises a memory 4 and a processor 5.

The biometric-based identification device 2 is part of the protected environment E or is capable of communicating electronically with the protected environment E to allow or deny access to the protected environment E by a purported user upon identification by the biometric-based identification system 1.

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, computer or computer networks such as management applications for configuring a computer or computer network or communication base station, electronic devices such as mobile phones or similar products, automated teller machines, restricted areas such as a laboratory or bank, and the like.

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, or is capable of electronic communication with, at least one biometric detector 9, 9', 9 ". In a simple embodiment, the biometric detector 9 is a fingerprint sensor. A complementary biometric detector 9', 9 ", if provided, may detect a different biometric characteristic.

The processor 8 of the biometric-based identification device 2 comprises at least one module 10, 10 ', 10 ", adapted to drive a respective biometric detector 9, 9', 9", so as to acquire a respective original electronic representation 11, 11 ', 11 ", of the biometric characteristic and to provide the original electronic representation 11, 11', 11", to the memory 7 of the identification device 2. In particular, when a user's finger is pressed against the sensor 9, a raw electronic image 11 of the fingerprint is acquired. The raw electronic image 11 may advantageously be in any of a variety of standard image formats, such as BMP, JPG, GIF, and the like.

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 the module AES4K from AuthenTec, Inc. of Melbourne, Florida, USA, and may, for example, be implemented by Microsoft Windows^TMThe driver subsystem communicates with the driver of the fingerprint sensor 9.

The processor 8 of the biometric-based identification device 2 further comprises at least one module 12, 12 ', 12 ", which is adapted to process the respective original electronic representation 11, 11 ', 11", and to provide a respective candidate biometric template 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 acquisition errors or noise due to, for example, ambient light, dust on sensitive surfaces, unevenness of sensitive surfaces, etc. The image processing module 12 is further adapted to extract from the fingerprint the most important features, such as the points where the fingerprint ridges diverge, converge or break, called minutiae, and to store candidate biometric templates 13, which are data structures comprising representative data for each minutia, in the memory 7 of the identification device 2.

As described in further detail below, in a preferred embodiment of the present invention, the candidate template 13 more specifically includes position data in the form of in-plane orthogonal coordinates X, y and orientation data t in the form of in-plane angles with respect to the X-axis. The orientation data t represents the general orientation of the fingerprint ridge in the context of the minutiae, as specified by the NIST-national standards and technical association.

The image processing module 12 may use a detail extraction algorithm from NIST and it may also include a module MinDetect, which is one of the types in whichhttp://fingerprint.nist.gov/NFIS/index.htmlAvailable open source code programs (at the date of filing of this patent application).

The complementary candidate template 13', 13 ", if provided, may include the same type of data as the candidate template 13, or may also include different types of data representing details acquired from different biometrics of the user, such as iris, retina, hand, face, and voice, signature, handwriting, and typing habits. The supplementary candidate templates 13', 13 ". may include, for example, 3D position data of a face template, or the time and duration of a peak or frequency of a speech signal.

The memory 4 of the smart card 3 is adapted to securely store at least one reference or enrolment template 14, 14', 14 ". The enrollment template 14, 14 ', 14 ",. is obtained at an initialization or enrollment step similar to the candidate template 13, 13 ', 13",. the user's identity is identified by the institution overseeing the protected environment E.

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

The biometric-based recognition 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 enrolled template 14. The matching module 15, in particular the finer matching module 17 in the identification device 2, is also adapted to compare the complementary candidate template 13 ', 13 ",. with the complementary enrolment template 14', 14",. and/or to compare the candidate template 13 with the enrolment template 14 more finely.

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

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 20 between the identification device 2 and the smart card 3.

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 mismatches determined by the coarser matching module 16 of the smart card 3 and may include enrollment templates 14, 14', 14 ", and any other sensitive data 21 stored in the memory 4 of the smart card 3, such as user personal data, digital certificates, user loyalty to control access to the protected environment E, and the like.

The secure channel submodule 18 of the identification device 2 may implement Microsoft cryptographics service provider, and the secure channel submodule 19 of the smart card 3 may implement Java cryptographics Extension. They can cooperate with each other by using the PKCS-public key encryption standard.

In the preferred embodiment, the secure communication channel 20 includes an asymmetric key encryption sub-module 22, preferably using the RSA standard, and a symmetric key encryption sub-module 23, preferably using the DES-data encryption standard.

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

The symmetric key encryption or DES sub-module 23 is in turn 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 the key container described by the CSP-Cryptographic service provider program of Microsoft Windows, or any other component that is typically based on the Unix's PKCS ° 11 standard.

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

Finally, the processor 8 of the biometric-based identification device 2 comprises a high-level module 30 adapted to interface with the protected environment E and with the smart card 3 and to coordinate the various modules of the processor 8 described above.

The high-level module 30 of the identification device 2 is preferably implemented as a dynamic library Win 32.

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

The high-level module 31 of the smart Card 3 is preferably implemented as a Java Card Applet for a Java Card OS and provides a plurality of APDU-application protocol data units for interfacing with the biometric-based identification device 2.

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

In an enrollment step 100, one or more biometric reference or enrollment templates 14, 14', 14 ",. are obtained from a user whose identity is recognized by the institution managing the protected environment E (step 101) and 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 the enrollment template is not fully described herein and this step 101 may be performed in many ways known in the art. In any case, reference may be made to a similar step 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, an identification step 104 is performed each time the purported user is to be identified, 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, the biometric-based identification system 1 is established by electronically communicating the portable data carrier with a processor or smart card 3, in which the template 14, 14', 14 ",. is stored, with the biometric-based identification device 2, i.e. the user presents the smart card 3 to the reader 6 (step 108); and the identification system 1 establishes a secure communication channel 20 (step 109).

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

The secure channel submodule 18 of the identification device 2 generates its private key 26 and its public key 27 and passes the public key 27 to the secure channel submodule 19 of the smart card 3. The secure channel sub-module 19 of the smart card 3 generates the session key 24, encrypts the session key 24 using 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 may also generate its private key 28 and its public key 29 and communicate 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 detector 9, 9 ', 9 ",. and the sensor driver module 10, 10 ', 10" and generated as 11, 11 ', 11 ",. This step may include the purported user pressing his/her finger on the fingerprint sensor 9, speaking into a microphone, or the like.

In a processing step 111, the original electronic representation 11, 11', 11 ",. The processing step 111 may comprise an image enhancement step 112 and a detail extraction step 113.

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

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

As a less preferred alternative, the enrollment template 14 is transferred to the identification device 2, still via the secure communication channel 20, and encrypted with the session key 24, and the matching step 115 is performed within the identification device 2 by its matching module 17. As a further less preferred alternative, the template communication step 114 is omitted by the matching being 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.

In 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 immediately denied (step 106). Alternatively, the biometric characteristic detection step 110, the processing step 111, the template communication step 114, and the matching step 115 may be repeated in the event of a mismatch, preferably no more than a selected number of times, as verified by the step 116 of comparing the number of attempts to a threshold.

In case of a match, a step 117 of unlocking the smart card functionality and the application may be provided. The smart card application may include a digital signature application, an encryption application, a mobile communication application, and the like.

More specifically, the functions and applications of the smart card 3 may include, for example, authentication functions conforming to standard 802.11, in particular, an EAP-extensible authentication protocol, such as EAP-SIM when the protected environment E is a GSM or mobile communication network, or EAP-TLS (transport layer security), such as when the protected environment E is a computer or a computer network, while the smart card 3 is used to exchange digital certificates, such as, for example, for securing E-mail messages, for securing access to a network or a computer or computer network application; when the protected environment E is a restricted area, contactless authentication applications based on RFID-radio frequency identification, etc.

The access enabling step 105 may comprise transferring the sensitive data 21 from the smart card 3 to the identification device 2 (step 118), preferably over the secure channel 20, and encrypting the sensitive data 21 with the session key 24, and forwarding the sensitive data 21 from the identification device 2 to the protected environment E (step 119).

In a particularly preferred embodiment, the biometric-based identification method comprises a two-level 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 computational resources, is a first or coarser matching step 115.

In case of a match in the first matching step 115, the allow 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, the second or finer matching step 121 is performed by the matching module 17 of the identification device 2 with a comparatively large amount of memory and computing functionality. The fine matching step 121 may comprise a finer comparison between the same candidate template 13 and enrollment template 14 that have been used by the smart card 3 in the coarser matching step 115, or may also comprise pairs of complementary enrollment templates 14 ', 14 "and candidate templates 13', 13", e.g. one or more comparisons between templates of more complex biometric data such as iris data, speech data, etc.

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

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

In case the result of the fine matching step 121 is a mismatch, the step 123 of locking the smart card 3 may be performed and access to the protected environment E is immediately denied (step 106) or returned to the biometric characteristic detection step 110 for further identification attempts, preferably not more than a selected number of times as checked in step 116.

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

Due to the limited memory and computational functionality required for the matching method, it is preferably used in the matching step 115, when implemented by the matching module 16 of the smart card 3, as a first or coarser matching step or as a single matching step of the biometric-based identification method. However, the matching method may also be advantageously used with electronic devices where resources are not limited, including the biometric-based identification device 2.

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

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

As mentioned briefly above, the data structure of each template 13, 14 comprises: for each detail thereof, position data in the form of in-plane orthogonal coordinates, such as 2D cartesian coordinates X, y, and orientation data t in the form of in-plane angles with respect to the X-axis.

More specifically, each biometric template 13(14) may be an array of short types of size 3M (3N), where M (N) is the number of details 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 detail,

item 3 h i +1 is the ordinate y of the ith detail,

item 3 i +2 is the orientation angle t of the ith detail.

The position data coordinates X, Y may be expressed in any length unit along the X, Y axis, and the orientation data t is preferably quantized, i.e. the orientation data t is expressed in unit angles u defined by a preselected ratio of one circumference angle. Preferably, the preselected ratio of the peripheral angles is 1/32, i.e., 11.25 °, as specified by the detail extraction algorithm from NIST.

Because during the extraction of minutiae from a detected fingerprint (step 113 of the biometric-based identification method outlined above), the orientation of each minutia is typically taken from a plurality of pixels of the original fingerprint image in the vicinity of the minutiae point, the use of such a relatively large unit angle u reduces the margin of error later in determining whether the two minutiae match in orientation. In fact, the same minutiae, and thus the same local orientation, will result in the same quantified angle in both fingerprints, regardless of the absolute orientation difference within the angular cell caused by the different orientation of the finger relative to the biometric detector 9.

Accordingly, if the detail of the candidate template 13 (registered template 14) is oriented at the angle α to the X-axis, its orientation data t will be set in the quantization step 202(203)

Wherein,represents the integer part of.

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

The displacement array L may be a short type of array of size 2 x D, where D is the number of displacement vectors between pairs of details from the candidate template 13 and the enrolled template 14 selected according to the similarity criteria described in detail below, where for 0 < ═ i < D:

the term 2 i +0 is the displacement ax along the abscissa x of the ith detail pair denoted by w below,

the term 2 i +1 is the displacement Δ y along the ordinate y of the ith detail pair, denoted below by z.

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

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

In step 207, the displacement array L is populated.

In the outer loop comprising M iterations, one detail from the enrolled template 14 is selected (step 209), as illustrated by step 208 comparing the pointer to M, while in the inner loop comprising N iterations, one detail from the candidate template 13 is selected (step 211), as illustrated by step 210 comparing the pointer to M.

For each pair of details m (xm, ym, tm), n (xn, yn, tn) selected in steps 209 and 211, an orientation data comparison is performed (step 212), in which it is checked whether the orientation data tm, tn of the two details differ by no more than a first threshold tlim, i.e. whether they differ by more than a first threshold tlim

|tm-tn|＜＝tlim (2)

Wherein, | represents the absolute value of.

It should be noted that the use of 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 enrolled 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 represented by the selected 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 details directed respectively at 112 ° and 113 ° will be represented in the biometric templates 14, 13 by the following angles:

when the result of the orientation data comparison step 212 is positive, the displacement vector V (w, z) is appended to the displacement array L in step 213, wherein

w＝xm-xn (5)

z＝ym-yn (6)

Pseudo code for one implementation of step 207 of filling the displacement array L will be given below:

for each minutia m(xm，ym，tm)of enrolment 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 above steps and the significance of the steps to be described in the matching method can be better understood with reference to fig. 5 and 6.

In these figures, M-8 details M1 to M8 of the registered template 14 are represented by solid shapes, and N-8 details N1 to N8 from the candidate template 13 are represented by open shapes. It should be noted, however, that the number of details M, N in the two templates is not always equal.

Similar detail-to-detail displacement vectors V1-V14 and V21-V35, as evaluated in the detail orientation comparison step 212, are shown in solid and dashed lines for greater clarity. In step 213, these displacement vectors V are appended to the displacement array L. In contrast, a displacement vector between a non-similar pair of details, an exemplary vector V' as shown by the dotted line between details n7 and m8 in FIG. 5, is neither calculated nor appended to displacement array L.

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

For ease of illustration, the two templates 13, 14 of fig. 5 and 6 are perfectly matched templates, i.e. they comprise exactly the same details. In fig. 5, the candidate template 13 has only been moved relative to the enrolled template 14, whereas in fig. 6 the candidate template 13 has only been rotated about the center C relative to the same enrolled template 14.

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

It will be seen that in fig. 5, the displacement vectors V1 through V8 have the same length and orientation, and in fact, each of them represents the actual translation of the enrolled template 14 to the candidate template 13. Vectors V9 to V14, on the other hand, differ in length and/or orientation in that they are derived from pairs of details n1, m6 which happen to have the same or similar orientation; n2, m 4; n4, m 2; n5, m 7; n6, m 1; n7, m 5.

It will be readily appreciated that in principle, when the finger has only a translation during detection of the candidate template relative to the position it had at the time of enrollment, if M and N are not equal because a portion of the finger's head is out of range of the biometric detector 9, the number of identical 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 through V14, will be statistically smaller, and any subset of the same pseudo-vectors will include fewer vectors.

Under real-life conditions, even considering pure translations of the two templates, the actual corresponding minutiae pairs n1, m1 from the two templates 13, 14 due to the calculations performed to extract minutiae from the detected fingerprint (step 113 of the biometric-based identification method outlined above); n2, m 2; .., the solid line displacement vectors V1 to V8 between n8, m8 actually differ slightly in length and/or orientation.

Furthermore, in the case where there is rotation between the templates 13, 14 (fig. 6), although in the case of the actual corresponding pairs of details n1, m1 from the two templates 13, 14; n2, m 2; .., n8, m8, the solid line displacement vectors V21 to V28 are also different in length and orientation. In particular, they will be chords of a circle centred on the centre of rotation C and passing through the detail pairs. Furthermore, pairs of details n1, m 6; n2, m 4; n4, m 8; n5, m 7; n6, m 1; n7, m 5; n8, a subset of pseudo displacement vectors V29 through V35 between m3, which are more similar in length-and less critical in orientation.

Also, in principle, when the finger is simply rotated during detection of a candidate template relative to the position it had when detecting the enrollment template, if M and N are not equal because a portion of the finger is out of range of the biometric detector, 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 through V35, will be statistically smaller, while any subset of the same pseudo-vectors will include fewer vectors.

In real-life conditions, the candidate template 13 will both translate and rotate relative to the enrolled template 14. It will be appreciated that the above principle still holds, in the case where the two templates 13, 14 are from the fingers of the same user, there will be several displacement vectors that differ only slightly in length and orientation between the actual corresponding pairs of details, being somewhat larger than a subset of the pseudo displacement vectors and being comparable to the minimum of M, N. Also, it is easy to understand that in case the two templates 13, 14 do not come from fingers of the same user, 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 low.

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

In case the maximum number Score is equal to or greater than the third threshold value Mlim, a match is returned in step 216, whereas in case the maximum number Score is lower than the third threshold value 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, Vs should be in terms of length and orientation, should in principle be a two-dimensional threshold. In practice, the difference of the vectors is the vector Δ V itself. However, the orientation of the difference vector Δ V is not of interest, since it is the relative orientation of the two displacement vectors that is important, not their absolute orientation. Thus, the threshold Range need only be equal to a threshold relating to the length or size of the vector.

Due to the choice of the data structure representing the displacement array V, each of which 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 limit value of each coordinate W, Z of the difference vector Δ V. The geometric meaning of such a displacement vector similarity criterion provides that the difference vector Δ V is inscribed in a square with sides Range.

The two displacement vectors Vr (wr, zr), Vs (ws, zs) will accordingly differ by no more than a second threshold value 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 the polar coordinates ρ, θ, then the threshold Range will be represented as a single graph, representing the limit of the radial coordinate ρ. The geometric meaning of such a displacement vector similarity criterion provides that the difference vector Δ V is inscribed in a circle with a radius Range.

The step 214 of obtaining the maximum number Score of the displacement vectors V that do not differ by more than the second threshold Range may be performed by comparing each pair of two displacement vectors Vr, Vs of the displacement array L against the threshold Range in equations (7), (8) above, and counting the number of successes.

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

First, in step 218, the displacement array L is sorted by the coordinates W. This is preferably performed using a known insert ordering algorithm which does not require any auxiliary arrays, since both array entries swap positions simultaneously.

A first displacement sub-array LW is then generated (step 219) by browsing the displacement array L, which is a relatively long subset of the terms of the displacement array L, whose W components differ by no more than a second threshold Range according to equation (7) above. Note that the verified W displacement sub-array LW can be stored in the same memory location as the displacement array L.

FIG. 4 shows in more detail the step 219 of generating the first or verified W displaced sub-array LW. In the outer loop, which includes a number of iterations equal to the number of entries in the displacement array L, D minus 1, one entry Lr (wr, zr) of the displacement array L is selected (step 221), as shown in step 220, which compares the pointer r to D, and in the inner loop, which includes D-r iterations, the following entry Vs (ws, zs) of the displacement array L is selected (step 223), as shown in step 222, which compares the pointer s to D-r. Then, equation (7) is checked in step 224, and if the check result is affirmative, the CurrentLength variable is incremented in step 225. At the end of the inner loop, the Maximum Length variable is stored as the Maximum of the previously stored CurrentLength and Maximum Length in step 226, and Max _ W _ index is stored as the current index r or the previously stored index Max _ W _ index, respectively, in step 227.

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

At the end of the outer loop 220, the item Lr (wr, zr) of the displacement array L where r is Max _ W _ index is selected and retained in the displacement sub-array VW where W is verified (step 228). Then, the shift array L is browsed again. In a loop comprising a number of iterations at most equal to D-r, a subsequent item Vs (ws, zs) in the displacement array L is selected (step 230), as shown by step 229, which compares the pointer s with D.

Then, formula (7) is checked in step 231, and if the check result is affirmative, the item Vs (ws, zs) is retained in the displacement sub-array VW of which W was verified in step 232. Returning to fig. 3, a second displacement sub-array LWZ is then generated (step 233), which is a relatively long subset of the terms of the first displacement sub-array LW, by browsing the displacement sub-arrays LW for which the Z-components differ by no more than a second threshold Range according to equation (8) above. Note that the second displacement sub array LWZ may be stored in the same memory location as the displacement array V and the first displacement sub array LW. Step 233 may be performed as described in detail above for step 219, mutatis mutandis.

The number of terms of the second displacement sub-array LWZ is then counted in step 234 and is the maximum number Score to be used in the comparison step 215.

It will be appreciated that the choice of the value of the threshold Range is critical to performing the matching method. If the selected value is too large, the displacement vectors between pairs of details from the enrolled template 14 and the candidate template 13 that do not actually correspond will be considered similar and the ratio of false matches will increase. Conversely, if the selected value is too small, the displacement vectors between the actual corresponding pairs of details from the enrolled template 14 and the candidate template 13 will be considered dissimilar, and the rate of false mismatch will increase, 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 matching method according to the invention may also be applied to candidate and enrollment templates 13, 14 comprising 3D position data, such as in case the biometric feature is a hand, a face or an iris of the user.

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).