Title of Invention

METHOD FOR BIOMETRICALLY VERIFYING A COMPARISON FINGERPRINT OF A PERSON AND CHIP CARD THEREFOR

Abstract

The invention relates to a method for biometrically verifying a comparison fingerprint (23) of a person on the basis of a reference fingerprint stored on a chip card (10) by means of comparing comparison minutiae (A', B1, C, D, E', F1) of the comparison fingerprint (23) with reference minutiae (A, B, C, D, E, F) i of the reference fingerprint for the purpose of authenticating a person by the steps: determining a baseline pair (A-B/A'-B'), consisting of two pairs of minutiae (A-A\ B-B') formed respectively by comparison minutiae (A', B') and reference minutiae (A, B) respectively corresponding to each other; determining third pairs of minutia formed respectively by comparison minutiae (C, D') and reference minutiae (C, D) respectively corresponding to each other ; determining as many as possible further pairs of minutiae of comparison minutiae (E1) and reference minutiae (E) respectively corresponding to each other; evaluating the comparison fingerprint of the person on the basis of the determined pairs of minutiae, wherein a person is regarded as authenticated, if the number of detected pairs of minutiae exceeds a predetermined threshold value ; wherein the determined pairs of minutiae define a chain starting with the pairs of minutiae (A-A', B-B') of the baseline pair (A-A\ B-B'), to which chain every determined pair of minutiae (C-C, D-D') is added, wherein the chain comprises at least three determined pairs of minutiae and wherein the order of the pairs of minutiae in this chain is invariable in the further course of procedure ; three relation pairs of minutiae (A-A', B-Br, C-C, D-Dr) are determined within the chain of all the determined pairs of minutia and that a further pair of minutiae (E-E1) is determined on the basis of the three determined relation pairs of minutiae by comparing geometrical relations between a selected reference minutia and the reference minutiae of the three pairs of relation minutiae with geometrical relations between a selected comparison minutia and the comparison minutiae of the three pairs of relation minutiae. The invention also discloses a chip card (10) for biometrically verifying a comparison fingerprint (23) of a person on the basis of a reference fingerprint.

Full Text

FIELD OF THE INVENTION [001] The invention relates to a method, a chip card, a system and a computer program product for verifying a fingerprint of a person. BACKGROUND OF THE INVENTION [002] The checking of the identity or an access authorization of a person is today widely carried out on the basis of biometric features of the person, which are difficult to forge. For this purpose at least one suitable biometric feature of the person, e. g. a fingerprint, an iris pattern, etc. is firstly determined as reference data in a registration step, and stored for later comparison to corresponding comparative data of the person. . [003] For reasons of security and feasibility it is expedient herein to store the reference data on a portable data carrier to be carried along by the person, for example a chip card or a smart card. For the verification of his/her identity, the person with the portable data carrier approaches a verification . device, which determines the corresponding biometric comparative data for comparison with the reference data stored on the data carrier. The comparison itself can then be carried out by both the device and, provided that the data carrier itself has computing power, by the data carrier itself. If a chip card with processor is used, the latter case, the so-called on-card matching, has security-technical advantages, since in a comparison taking place on the chip card the sensitive reference data remain in a particularly secured memory of the chip card. [004] Since current systems for on-card matching mostly use proprietary data formats, for the sake of improved interoperability standardized data formats are increasingly defined and employed. However, compared to the technically and algorithmically optimized proprietary data formats, standardized data formats usually have the disadvantage that the comparison of biometric features of a person on the chip card is possible only at a partly substantially higher execution time. An important factor herein is in particular that conventional comparison methods mostly proceed iteratively and insofar in a particularly time-consuming manner. [005] A particularly suitable biometric feature for the verification of identity is a person's fingerprint. However, since this complex information cannot be used as such for comparison, specific characteristic features of the fingerprint - so-called "minutiae" - are first extracted, which features describe the characteristic line courses of the ridge pattern of a finger print, such as e. g. line ends or divisions (bifurcations). [006] For the verification of a person's identity a comparison fingerprint of the person is compared to a reference fingerprint, by extracting comparison minutiae from the comparison fingerprint, in order to compare these with the reference minutiae extracted beforehand from a reference fingerprint and provided on the chip card. As many pairs of minutiae, consisting of reference minutiae and comparison minutiae corresponding to each other, are determined and evaluated on the basis of local-geometrical criteria. The determination of pairs of minutiae can in principle be divided into two steps: determining a baseline pair consisting of two pairs of minutiae and, proceeding from the baseline pair, determining as many as possible further pairs of minutiae. Therein the baseline pair is determined on the basis of absolute criteria (e. g. identical location, position or local properties of the minutiae in the respective fingerprints), whereas the further pairs of minutiae are determined in dependence on the already determined baseline pair or relative thereto. [007] However, this procedure requires mostly nested (iterative or recursive) calculation processes, in order to find as many pairs of minutiae as possible and to be able to guarantee a high degree of reliability of the result. In such optimization procedures usually also particularly elaborate correction operations are necessary, since already found pairs of minutiae frequently turn out to be local optima and have to be discarded, in order to achieve a better solution and higher reliability by a revised new calculation. US 2003/0044052 Al discloses a method and a system for comparing a set of minutiae of a current image with a set of minutiae of a reference image, according to which the minutiae are sorted by their Cartesian coordinates in the image plane from a predetermined point of origin, a common path of similar minutiae is searched in the reference set and in the current set, and it is considered that there is an identity between the two images if the common path is comprised of a number of segments greater than a first threshold. The search starts based on a first pair of minutiae, the baseline pair, that is present both in the current image and the reference image. Once this baseline pair is found, a further minutiae in the reference image is searched based on pair of minutiae that has been found in the preceding step. A segment formed in this way is compared to a potential segment in the current image. Since the search for a new segment is always only based on the pair of minutiae that has been found in the preceding step, there is a rather high probability that a wrong minutiae in the current image is selected, due to the tolerances in length and orientation which have always to be considered. Consequently, the respective method is rather slow and error-prone. [008] It is consequently the object of the present invention to provide a fast, but nevertheless reliable and secure verification of fingerprints. [009] This problem is solved according to the invention by a method, a chip card, a system and a computer program product having the features of the independent claims. In claims dependent on these advantageous embodiments and developments of the invention are specified. [0010] In the comparison of comparison minutiae and reference minutiae according to the invention a chain is defined, consisting of all already determined pairs of minutiae, including the two pairs of minutiae of the baseline pair, which chain defines a sequence of the pairs of minutiae that is invariable in the further course of the procedure, and to which each further determined pair of minutiae is added. Each pair of minutiae is then determined on the basis of geometrical relations of the minutiae in question to the minutiae of three already determined relation pairs of minutiae defined through their position within the chain. [0011] As relation pairs of minutiae the pairs of minutiae at certain positions within the chain of the already determined pairs of minutiae are used, so that a new pair of minutiae is verified in relation to these three already determined pairs of minutiae. Then certain relations of a selected reference minutia of a potential further pair of minutiae to the reference minutiae of the three pairs of relation minutiae are calculated and compared to the values of the same relations of a selected comparison minutia, potentially corresponding with a selected reference minutia, to the comparison minutiae of the three relation pairs of minutiae. In the case that all detected values of the selected comparison minutia are within certain tolerance ranges of the corresponding values of the selected reference minutia, it is assumed that the selected comparison minutia and the selected reference minutia correspond to each other and form a pair of minutiae, which is added to the chain as currently latest link. [0012] A person is for example regarded as authenticated, if the chain reaches a predetermined minimum length, that is, the number of detected pairs of minutiae exceeds a predetermined threshold value. [0013] In the simplest case the procedure is carried out in such a way that, when further pairs of minutiae are determined, first a reference minutia is selected which lies within certain local surroundings in the vicinity of the reference minutia of the pair of minutiae detected most recently, and that for the verification of relations comparison minutiae are selected which lie in the same local area of the comparison fingerprint (thus have similar position coordinates) as the reference minutia in the reference fingerprint. Firstly all relations of a reference minutia can be calculated in order to check the amount of comparison minutiae for whether there is at least one comparison minutia whose relation values are within the tolerance range of the relation values of the reference minutia. In the case that there are several such comparison minutiae, the minutia can be chosen whose relations differ least from those of the selected relation minutia. [0014] By forming the chain of all pairs of minutiae determined so far and determining three relation pairs of minutiae within this chain, the number of necessary comparisons between comparison minutiae and reference minutiae is drastically reduced in relation to conventional methods, which leads to a considerable acceleration of the procedure, since comparisons have to be made only with the three pairs of relation minutiae. The required reliability and exactness of the results is ensured by also evaluating such relations which establish in particular a geometrical relation of a selected minutia to the minutiae of already determined pairs of minutiae, in addition to such values which represent merely local features of a minutia (e. g. its position in the fingerprint or its minutia angle). [0015] The described method can be carried out by a chip card designed according to the invention, comprising a processor and a memory arrangement with a nonvolatile EEPROM memory in particular. Preferably the inventive method is carried out by a biometrics module designed as a software program and provided on the chip card (either in the EEPROM or in the ROM memory). Alternatively, also a hardware solution, e. g. in the form of a biometric co-processor, is thinkable. [0016] The chip card furthermore comprises a certain memory area or a separate memory for storing the reference minutiae, wherein this memory preferably fulfills special security requirements, in order to ensure the security of the sensitive biometric data. [0017] When the chip card is employed, a person brings the chip card into contact with a verification device (terminal) and supplies a comparison fingerprint via a biometric sensor provided there for this purpose. Via corresponding data communication interfaces the comparison fingerprint is transmitted to the chip card, where the fingerprint is stored in a memory area provided for this purpose and the comparison minutiae are extracted. [0018] In a preferred embodiment the pairs of minutiae situated in the first, the penultimate and ultimate position of the chain are selected as relation pairs of minutiae. Therein the first pair of minutiae of the chain is one of the two pairs of minutiae of the baseline pair, whereas the penultimate and the ultimate pair of minutiae of the chain represent the two pairs of minutiae determined most recently. Of course also different or more relation pairs of minutiae can be determined on the basis of their position in the chain, e. g. all pairs of minutiae at even or odd positions of the chain. [0019] As relations to be evaluated in the development of further pairs of minutiae it is particularly advantageous to determine the distance of the selected reference minutia or comparison minutia to the respective reference minutiae or comparison minutiae of the relation pairs of minutiae. As further relation values to be compared it is possible to evaluate the angles, which are enclosed by an imaginary line from the selected reference minutia or comparison minutia to the reference minutia or comparison minutia of the ultimate pair of minutiae and further on to the reference minutia or comparison minutia of the penultimate pair of minutiae. Of course additionally or alternatively also further angles formed in this manner by means of the relation pairs of minutiae can be evaluated. [0020] Moreover, as a local feature of a minutia the minutia angle of a selected reference minutia or comparison minutia can be evaluated, which describes the orientation of the groove extending from the minutia in the corresponding fingerprint in a reference coordinate system. [0021] In order to optimize the execution speed of the method, it is possible in a preferred embodiment to firstly compare .the minutia angles of the selected reference minutiae and comparison minutiae by way of a preselection, since this requires the least computing time. Only in the event that the minutia angles lie within the predetermined tolerance range, further relations are calculated, since the selected minutiae otherwise do not correspond to each other anyway. [0022] In the case that the minutia angles he within the predetermined tolerance" range, the distances of the selected minutiae to the corresponding minutiae of the relation pairs of minutiae can be calculated next on the basis of an estimate of computing time, and, in the case that also the distances lie within the corresponding tolerance ranges, only finally the angles enclosed by the selected minutiae and the corresponding minutiae of the relation pairs of minutiae, since this requires the most complex calculation. [0023] In the case that a selected comparison minutia does not correspond to a selected reference minutia, i. e. they are not identical in the corresponding reference fingerprint and comparison fingerprint, the determination of a pair of minutiae is repeated with the same selected reference minutia, but with a different comparison minutia, until according to predetermined criteria (e g. a maximum number of attempts) it seems improbable that a comparison minutia corresponding to the selected reference minutia can be found. [0024] In view of a preferably efficient comparison of reference minutiae and comparison minutiae it is expedient to presort the comparison minutiae on the basis of their minutia angles during or directly after their extraction from a reference fingerprint, or to store them in a pre-sorted order in a memory area of the chip card provided for this purpose, in order to be able to select a comparison minutia matching a selected reference minutia on the basis of its minutia angle as quickly as possible. In addition, it can be expedient to calculate the angles, distances or further relations of the reference minutiae only when they are needed for the determination of a corresponding comparison minutia. Such already calculated angles and distances can then be stored for possible further comparisons with other selected comparison minutiae in a suitable data structure together with the corresponding comparison minutiae in a nonvolatile (EEPROM) memory of the chip card. [0025] In a particularly preferred embodiment the order in which the reference minutiae are considered when determining pairs of minutiae is already specified by a predetermined sequence of reference minutiae before the comparison of fingerprints. This can already be carried out during the recording of the reference fingerprint and the extraction of the reference minutiae. In this case, in the comparison between the reference minutiae and the comparison minutiae, a reference minutia is not selected individually in dependence on predetermined selection criteria or the pairs of minutiae determined beforehand, but a certain path of the reference minutiae is predetermined through the reference fingerprint, which also determines the same path of the comparison minutiae through the comparison fingerprint, so that by limiting the possibilities of combination a further acceleration of the procedure can be achieved. [0026] Herein it is in particular possible that, if no matching comparison minutia can be found for a certain reference minutia, the determination of a further pair of minutiae is carried on with the subsequent reference minutia specified by the sequence of reference minutiae. Since the determination of further pairs of minutiae is thus no longer blocked by a "bad" comparison minutia, more reliable comparison results are achievable, without adversely affecting the speed of the procedure. A further acceleration of the procedure without any detectable loss of reliability can be achieved if only such baseline pairs are admitted which immediately follow each other in the predetermined sequence of reference minutiae. [0027] In this especially preferred embodiment of the invention it is advantageous to establish the sequence of reference minutiae already during the extraction of the reference minutiae from a reference fingerprint This can be done by means of certain predetermined criteria, which are specified on the basis of a quality, relevance or statistical significance or on the basis of geometrical criteria for the reference minutiae. Herein it is particularly expedient to weight the reference minutiae according to their minutia angles, according to their distances to adjacent minutiae, according to the position of the minutia within the fingerprint (e. g. a minutia in the center of the fingerprint can be more important than one in the periphery), or according to confidence values, which are calculated during the image-analytical extraction of the comparison minutiae from the comparison fingerprint. BRIEF DESCRIPTION OF THE DRAWINGS [0028] Further characteristics and advantages of the invention will result from the following description of a variety of exemplary embodiments and alternative embodiments according to the invention in connection with the accompanying drawings. The figures are described as follows: [0029]Figure 1 types of minutiae in a schematic fingerprint image; [0030]Figure 2 criteria for determining a baseline pair; [0031 ]Figure 3 criteria for determining further pairs of minutiae; [0032]Figure 4 skipping a reference minutia when determining a further pair of minutiae; [0033]Figure 5 a flowchart of a chain match procedure.according to the present invention; ■ ":. [0034]Figure 6 an example for forming a chain in a particularly preferred embodiment of the invention; and [0035]Figure 7 an inventive chip card. DETAILED DESCRIPTION OF THE INVENTION [0036] Figure 1 shows two schematic portions of the courses of the ridges.of a fingerprint. Therein the ridges form minutiae as characteristic points. The two most important types of minutiae are ridge endings (left) and ridges which divide into two new ridges (ridge bifurcation; right). Although in two prints of the same finger the type of minutia should be identical in the same minutia, an evaluation of the type of minutia generally does not lead to any advantage and can therefore be neglected. [0037] The inventive method is in principle a comparison algorithm (matcher), which firstly searches a start feature which is common to the reference template and the comparison template. (A template is the data set of the minutiae extracted from a digitized fingerprint image). Starting from these start minutiae as many as possible further minutiae corresponding to each other are searched. Roughly, thus two steps are carried out: a search for an initial double pair of minutiae corresponding to each other (so-called baseline pair), and a subsequent search for matching pairs of minutiae. If sufficient minutiae corresponding to each other have been found (depending on the desired security), it can be assumed with a certain probability that the fingerprints belong to the same finger. [0038] In the sense of this invention a baseline consists of two minutiae within one template, proceeding from which further minutiae can be searched or compared. It serves as the basis for further steps. A baseline pair is correspondingly formed by minutiae respectively in the reference template and the comparison template, which, after the calculation of a variety of parameters, are regarded as identical. Thus a baseline pair is a pair of baselines in the reference template and in the comparison template corresponding to each other. ■_. . [0039] The comparison of minutiae is started with a baseline pair. In order for the respectively two minutiae from the reference template and the comparison template to form a baseline pair, the criteria illustrated in Figure 2 have to be fulfilled. Respectively two points from each of the two templates are shown. The reference minutiae A and B are matched by the comparison minutiae A' and B\ Algorithmically, first a minutia A is selected in the reference template, a corresponding minutia A' is determined in the comparison template (a = a' ± maximum rotation of the prints) and a further point B is selected. In order to find a matching point B', firstly the values d, y and p-(ct-a') are pre- calculated. Now all possible points in the comparison template are considered which have a certain minutia angle (p' = p-(a-ct') + minutia-angle tolerance). Finally, d' and y' are calculated, which have to lie within the distance tolerance, or the tolerance of the x axis of the minutia angle. If this is the case, a baseline pair has been found. [0040] For the decision whether a' lies within the maximum rotation, only an addition is necessary (in addition to the comparison itself). In the case that the tolerance is e. g. TI/4, 75% of the possible baseline pairs are already inapplicable. The values d, y and p-(a-a') are calculated in advance, since they are needed repeatedly in the search for B'. Since the minutiae in the comparison template are pre-sorted according to the minutia angles, only a small number of minutiae are considered in the search of B'. The search in the sorted list starts with the minutia whose p' is just big enough to lie within the tolerance, and ends with the first minutia whose p' is too big. At this stage almost all false possibilities for baseline pairs have been ruled out, now only d' and y' have to be calculated and compared. In the case that the tolerance for p' is so small that the values d' and y' almost never have to be calculated, a variant can be used in which d, y are calculated only when necessary. The additional effort for checking the necessity then has to be smaller than the effort economized through the frequent non-calculation of d, y. [0041] The basic idea of the inventive method is the chain matching, thus the search for an as long as possible chain of matching pairs of minutiae. Therein the respectively subsequent pair has to match the first, the penultimate and the ultimate of the already found pairs of minutiae of the chain, consequently match three already found pairs of minutiae. Since the new pairs of minutiae always have to geometrically match the pairs found most recently, a chain of pairs of minutiae is formed. [0042] As illustrated in Figure 3, the following criteria are checked in order to find a further pair of minutiae matching the chain: The distance between the new, potential minutia (in the following referred to as E) to the first (A), penultimate (C) and ultimate (D) minutia, the minutia angle of E, as well as the angle between the line segments C-D and D-E. [0043] There are some criteria herein whose checking requires a certain computing time, namely the three distances and the angle a. However, there is a simple possibility for not having to carry out some of the calculations: A comparison is discontinued immediately if a criterion lies outside a predetermined tolerance range. This means that the second criterion is checked less frequently than the first, the third less frequendy than the second, and so on. It frequently happens that the fifth criterion is not required at all, since all possible pointsin the comparison template fail to fulfill the preceding four criteria. This finding involves two possibilities of optimization: Optimal checking order of the criteria: Here, the angle p is the easiest to check, since this value does not have to be calculated and only the rotation of the prints has to be taken account of. Thus only an addition (due to the rotation) and a comparison (with p' in the comparison template) are necessary. Since the comparison minutiae are pre¬sorted according to the angles p, p furthermore has to be checked only in regard of a few minutiae. Distance calculations are marginally faster than the calculation of the angle a, so that the distances are calculated first, and a last. "On demand" calculation of values in the reference template: Only when a distance (di, dn and dn.i), or the angle a has to be checked are the values in the reference template calculated. Once the value has been calculated, it is re-used for the search of a counterpart of the current point (point E in Figure 3). Consequently, an additional comparison is necessary every time, checking whether the value has already been calculated or not. However, this loss of time is smaller than the gain of time through the non-calculation of the unneeded values. [0044] First a baseline pair is searched algorithmically, and an as long as possible chain of matching pairs of minutiae is formed. If no further pair of minutiae can be found, no attempt is made to find a different chain matching the current baseline pair. The time requirement for a comparison would become extraordinarily high (if all possible chains are searched), whereas the error rates are practically not improved at all. [0045] It can of course happen that an incorrect pair of minutiae has crept into the chain (provided that two prints of the same finger are compared). In this case there are two possibilities: 1. The chain is continued, since the incorrect minutia in the comparison template is almost identical to the right minutia in the reference template. This is the typical case. 2. The chain stops, since the correct pairs of minutiae no longer match the chain. [0046] In Figure 4 firstly a correct baseline pair is calculated (A-B/ A'-B')- However, as a match for the minutia C, instead of C\ D' is erroneously found. The result is that the chain only reaches a length of three instead of five. For the above example it was implied that the pair of minutiae CI D' still lies within the search tolerances, and that the further combinations D/ C, D/ F, E/ C and E/ F lie outside these tolerances (in E/E' e. g. the difference of a and a' is too big). [0047] In the case that no further pair of minutiae is found, it cannot be checked whether there is an "incorrect" pair of minutiae in the chain, there is no indication whether a longer chain exists or not. Trying out a variety of chains is no alternative for reasons of time efficiency. However, if there are sufficient matching pairs of minutiae, there are also abundant baseline pairs which can be found. Therefore the algorithm compares the length of the current chain to the maximum so far (which is initialized with one), and updates the maximum if required and carries on with the next baseline pair. If there are sufficient pairs of minutiae, it is highly probable that a chain matching at least one baseline pair is found, which chain is long enough, so that the result of the comparison is positive. [0048] The maximum chain length achievable is important for the score, i. e. the assessment whether the corresponding comparison template has to be judged correct. The size of the templates is also taken into account in the calculation of the score. Herein, score values with the geometric average of the template sizes are best: [0049]If the baseline pair is considered to form part of the length and the number of minutiae in the reference template and in the comparison template is identical, the maximum score is 1. In order to avoid the root, the numerator and the denominator can be squared. [0050]The overall algorithm is shown in Figure 5 with the loops for the baseline search and for the search of further pairs of minutiae. Herein a chain is an array storing the current chain with a pair of minutiae per index, "maxchainlength" stores the number of pairs of minutiae of the longest chain found so far, and "threslength" is the length at which the comparison can be exited successfully. [0051]In the search for further links in the reference template only such minutiae are taken into account, which have a higher index than the link found most recently. This limitation has the advantage that on average only half of the minutiae coming into question for the respectively subsequent link are considered. Furthermore, the checking of the reference template for minutiae already forming part of the chain is omitted, since all of these have a lower index than the minutia found most recently. Depending on the database, the algorithm can be accelerated by approximately 30% through this optimization. The error rates remain almost constant, since minutiae with a lower index than the minutia found most recently were already considered and rejected at least once. It is highly improbable that it can be incorporated in the chain in a different location. [0052]When storing the chains, all indices of the comparison minutiae are stored in the EEPROM memory of a chip card, in order to make sure that one minutia is not incorporated in the chain several times. It is unnecessary to store all indices of the reference minutiae, since this problem can be solved algorithmically, by having the indices of the reference minutiae in the chain increase strictly monotonously. In this manner, only three indices of the reference template are required for every continuation of the chain: the indices of the first, the penultimate and the ultimate minutia. In this manner, only three bytes have to be reserved for the list of reference minutiae. [0053] The indices of the baseline minutiae in the reference template may differ at the most by one predetermined value (e. g. 4). The idea behind this optimization is that it is not necessary to try out all possibilities for baseline pairs. If e. g. the baseline pairs with the indices 0-1, 0-2, 0-3 and 0-4 do not lead to any success in the reference template, it can be assumed that the minutia in the reference template with the index 0 does not have a counterpart in the comparison template. Algorithmically therefore checking is expedient in any case (e. g. as a loop exit criterion). [0054] In the following the substantial points of the inventive chain matcher are listed one after another: Use of the arcus tangens function instead of the conventionally used arcus cosinus function for determining angles. Pre-sorting of the comparison template according to minutia angles. The first comparison criterion is consequently always the minutia angle. Distances are not calculated in advance, since through the prior checking of minutia angles comparatively few distances are really needed, so that an advance calculation in table form would even have a negative impact on the time requirement. Consequently no memory consumption for a distance table. The values of some comparison criteria are calculated "on demand" in the reference template. . The search for baseline pairs is sufficiently exact and uses more criteria for checking. Thus fewer incorrect baseline pairs are used. Use of one minutia type bit for the minutia angle, i. e. for angles always eight bits are necessary. In this manner, no conversions are necessary. Structure-optimized source code in order to improve runtime. [0055]An especially preferred embodiment of the above described chain matcher is the "fast chain matcher". The basic idea of the fast chain matcher is that during the enrollment, i. e. the recording of the reference fingerprint, one single chain is specified in the reference template, which chain is then searched in the comparison template during the verification. In the case that the specified chain cannot be found, the comparison is discontinued negatively. [0056]In principle the fast algorithm is identical to that of the normal chain matcher. ■ However, there is the difference that only specific baseline pairs are admitted. The selection of these specific baseline pairs is decisive for the results. The idea behind it is that it is decided during the enrollment which path the chain may take through the reference template. Other paths are not admissible. What is important is to find a path which delivers optimal results. A specific path means the following: The reference template has to be sorted in accordance with this path during the enrollment. The indices of the reference minutiae in one baseline pair have to differ by exactly one. If one link is missing in the predetermined chain (thus if for one minutia in the reference template no minutia can be found in the comparison template), this links is to be left out and the next link is to be carried on with. [0057]The first item in the above list serves as simplification of the other two items. In principle this specified path can also be stored on the chip card, e. g. in the EEPROM memory, however, if the minutiae of the reference template are sorted in accordance with this path, no further memory has to be taken up on the chip card. Such a sorting then implies the second item, that the indices of the reference minutiae in one baseline pair are always next to each other. Since it can of course happen that not all minutiae of the reference template are present in the comparison template, a gap in the path has to be accepted (third item of the above list), otherwise only very many small chains would be found instead of one big chain. [0058] Figure 6 illustrates an example thereof. For the minutiae A, C, D and F in the reference template Oeft) there are equivalents in the comparison template (right), but not for the minutia B, whose index is between the indices of the minutiae A and C, and for the minutia E, whose index is between the indices of the minutiae D and F. The normal chain matcher would find the following chains (of course always with the corresponding counterpart in the comparison template): baseline A/ C, further minutiae D and F baseline A/ D, further minutia F baseline A/ F, no further minutiae baseline C/ D, further minutia F baseline C/ F, no further minutiae baseline D/ F, no further minutiae [0059]The maximum chain length consequently is 4. Since in the fast chain matcher the indices of the baseline in the reference template may only differ by one, only one chain is found by this algorithm: baseline C/ D, further minutia F. [0060] Here the maximum chain length amounts to only 3. It is clearly obvious from this example which results are to be expected: the speed is greatly increased, the error rates become slightly inferior. Considering the example, an alternative is expedient, in order to slightly improve the error rates again, the search for further pairs of minutiae is not limited by admitting only such reference minutiae which have a greater index than the indices of the reference minutiae in the baseline pair. Consequently, the chain is not only searched forward, but also backward. In the above example, (again exactly) one chain would be found: baseline C/ D, further minutiae A and F. [0061] Consequently the chain length also amounts to 4 here. This variant promises better error rates, which measure up to those of the normal chain matcher, however at the cost of time. [0062] The greatest problem in the fast chain matcher is to find the optimal path during the enrollment. In many systems already today several prints are taken during the enrollment, in order to either select the best print, or to amalgamate the minutiae of all prints to form one new, optimal template (which is as a rule not carried out on the chip card, but externally, on a faster processor). In this procedure also the search for the optimal path could be implemented. Therein it is very important that secure minutiae, which are present in almost all prints, follow one another (important for both variants) and lie at the start (for the first variant of the fast chain matcher), since it is highly probable in this manner that baseline pairs can be found with the aid of these minutiae. A further idea for pre-sorting is that additional attention is paid to the fact that the distances between the adjacent (according to the index) reference minutiae are great enough, so that the corresponding baseline pairs are a priori situated outside the numerically inexpedient range. However, it has also to be taken into account that fingerprints are frequently very distorted, so that baselines which are too long frequently do not lead to an ideal result [0063] In order to use the possibilities for searching the optimal path, the following ways of sorting (the index order represents the optimal path) can be carried out in the reference template: none, sorting according to minutia angles (like in the comparison template), random sorting (two results are listed respectively), distances between two adjacent points if possible greater than dxMax/4 and smaller than dxMax/2. Therein dxMax represents the maximum difference between the x- coordinates of two minutiae in the reference template. [0064] These types of sorting have the advantage that they are very fast and can thus take place on the chip card during a comparison. It must be kept in mind that as reference template always the template with the fewer minutiae is chosen. If the search for the optimal path is carried out during the enrollment, the templates cannot be swapped (easily) any longer. [0065] Figure 7 is a schematic view of a chip card 10, which is connected via interfaces 15, 22 corresponding with each other to a verification device 20, e. g. to an authentication terminal for a secure building section, an automatic teller machine or another security device. The chip card 10 comprises a processor 14 and a storage hierarchy, consisting of a permanent ROM memory 11, a nonvolatile and rewritable EEPROM memory 12 and a volatile RAM working memory 13. In the ROM memory 11 an operating system 16 (e. g. JavaCard) resides, which provides the basic functions of the chip card, such as input and output or memory organization, as well as chip-card-specific functions, such as cryptography and authentication. Among other things, a biometrics module 17 is integrated in the operating system, which implements one of the above minutia match methods for comparing fingerprints. Likewise, the inventive comparison method could also be present as a separate software component in the EEPROM memory 12 (e. g. as Java applet) or could also be implemented as a hardware solution in the form of a biometric co-processor. [0066] In the EEPROM memory 12 a memory area 18 is arranged, in which a data set of the reference minutiae 19 was stored during the enrollment and setup of the chip card 10. ■ The reference minutiae 19 are as a rule extracted from a recorded reference fingerprint in a separate step and stored in the memory area 18 of the chip card 10. Although this is the usual procedure, it is in principle also possible to store the complete reference fingerprint in the memory area 18 and to extract the reference minutiae 19 only on the chip card 10. [0067]For an especially preferred embodiment of the present invention the reference minutiae 19 can be stored in the memory area 18 as a pre-sorted sequence, in order to determine in the order thus specified comparison minutiae corresponding to the reference minutiae 19 for forming pairs of minutiae. [0068] Of course the memory area 18 for the reference minutiae 19 can also be in the ROM memory 11. However, in this case the reference minutiae 19 have to be extracted and loaded in the ROM memory 11 already during the production of the chip card 10 or the loading of the operating system 16. It is expedient in any case to embody the memory . area 18 as a particularly secured memory area, in order to sufficiently protect the reference minutiae 19 as biometric reference information. [0069] When a user of the chip card 10 approaches a verification device 20 in order to prove his access authorization by means of a biometric authentication, a sensor 21 firstly . records and digitizes his comparison fingerprint 23. The sensor 21 can e. g. be an optical sensor, for example a CCD camera, which directly produces a digital image, or an ultrasonic sensor. Subsequently the comparison fingerprint 23 (in plain text, compressed or encrypted) is transmitted to the chip card 10, where it is stored in the EEPROM memory 12 for further processing. [0070] The comparison or the matching itself is then carried out by the biometrics module 17, by extracting the comparison minutiae from the comparison fingerprint 23, in order to check their correspondence with the reference minutiae 19 according to one of the methods described above. On the basis of a sufficient correspondence of the comparison minutiae and the reference minutiae 19, evaluated on the basis of given criteria, it can be assumed that the comparison fingerprint 23 corresponds to the reference fingerprint and finally that the person is authorized WE CLAIM : 1. Method for biometrically verifying a comparison fingerprint of a person on the basis of a reference fingerprint by means of comparing comparison minutiae (A', 5 B', C, D', E', F) of the comparison fingerprint with reference minutiae (A, B, C, D, E, F) of the reference fingerprint for the purpose of authenticating a person by the steps: determining a baseline pair (A-B/A'-B'), consisting of two pairs of minutiae (A-A1, B-B') formed respectively by comparison minutiae (A', B') and reference minu¬ tiae (A, B) respectively corresponding to each other; 10 determining third pairs of minutia formed respectively by comparison minutiae (C, D') and reference minutiae (C, D) respectively corresponding to each other; determining as many as possible further pairs of minutiae of comparison minutiae (E1) and reference minutiae (E) respectively corresponding to each other; 15 evaluating the comparison fingerprint of the person on the basis of the determined pairs of minutiae, wherein a person is regarded as authenticated, if the number of detected pairs of minutiae exceeds a predetermined threshold value ; characterized in that the determined pairs of minutiae define a chain starting with the pairs of 20 minutiae (A-A1, B-B') of the baseline pair (A-A1, B-B'), to which chain every determined pair of minutiae (C-C, D-D') is added, wherein the chain comprises at least three determined pairs of minutiae and wherein the order of the pairs of minutiae in this chain is invariable in the further course of procedure; 25 three relation pairs of minutiae (A-A', B-B', C-C, D-D') are determined within the chain of all the determined pairs of minutia and that 30 a further pair of minutiae (E-E') is determined on the basis of the three determined relation pairs of minutiae by comparing geometrical relations between a selected reference minutia and the reference minutiae of the three pairs of relation minutiae with geometrical relations between a selected comparison minutia and the 5 comparison minutiae of the three pairs of relation minutiae. 2. Method as claimed in claim 1, wherein as relation pairs of minutiae the pairs of minutiae disposed in the first, the penultimate and the ultimate position of the chain are used. 10 3. Method as claimed in claim 1 or 2, wherein when determining the further pair of minutiae, the distances of the minutiae of the further pair of minutiae to the corres¬ ponding minutiae of the relation pairs of minutiae are taken account of in the rela¬ tions. 15 4. Method as claimed in one of claims 1 to 3, wherein when determining the further pair of minutiae, the angles enclosed by the minutiae of the further pair of minutiae and the corresponding minutiae of the ultimate and the penultimate pair of minutiae of the chain are taken account of in the relations. 20 5. Method as claimed in one of claims 1 to 4, wherein a minutia has a minutia angle and that when determining the further pair of minutiae the minutia angle of the comparison minutia of the further pair of minutiae is compared to the minutia angle of the reference minutia of the further pair of minutiae. 25 6. Method as claimed in claim 5, wherein when determining the further pair of minutiae, the minutia angles are compared first, and the determining is discontinued if these angles do not lie within a predetermined tolerance range. 30 7. Method as claimed in claim 6 with 3, wherein after comparing the minutia angles of the minutiae of the further pair of minutiae, the distances of the minutiae of the further pair of minutiae are compared, and the determining is discontinued if these distances do not lie within predetermined tolerance ranges. 5 8. Method as claimed in claim 6 or 7, wherein in that when the determining of the further pair of minutiae is discontinued, this determining is carried out again with a different comparison minutia and/or a different reference minutia. 10 9. Method as claimed in one of claims 1 to 8, wherein the comparison minutiae are sorted in accordance with their minutia angles before the comparison with the reference minutiae takes place. 10. Method as claimed in one of claims 1 to 9, wherein the comparison 15 fingerprint of the person is evaluated as soon as no further pair of minutiae can be determined. 11. Method as claimed in one of claims 1 to 10, wherein when determining the further pair of minutiae, angles and/or distances of reference minutiae are calculated 20 only when they are needed for comparison with angles and/or distances of the corresponding comparison minutiae. 12. Method as claimed in claim 11, wherein calculated angles and distances are stored for further comparisons. 25 13. Method as claimed in one of claims 1 to 12, wherein the order of the reference minutiae to be considered when determining the baseline pairs and further pairs of minutiae is determined by a predetermined sequence of reference minutiae. 30 14. Method as claimed in claim 13, wherein, if no pair of minutiae can be determ¬ ined for a reference minutia in the order predetermined by the sequence of reference minutiae, the process is carried on with the subsequent reference minutia. 5 15. Method as claimed in claim 13 or 14, wherein when forming the baseline pair, only such reference minutiae are taken into account which follow each other directly in the sequence of reference minutiae. 10 16. Method for providing reference minutiae of a reference fingerprint for the biometric verification of a comparison fingerprint of a person on the basis of reference minutiae as claimed in any of claims 1 to 15, wherein from the extracted reference minutiae a sequence of reference minutiae is determined on the basis of predetermined criteria, and is provided together with the reference minutiae. 15 17. Method as claimed in claim 16, wherein the sequence of reference minutiae predetermines the order in which, when verifying the comparison fingerprint, corresponding comparison minutiae of the comparison fingerprint are determined for the reference minutiae. 20 18. Method as claimed in claim 16 or 17, wherein the sequence of reference minutiae is determined on the basis of minutia angles of the reference minutiae. 19. Chip card (10) for biometrically verifying a comparison fingerprint (23) of a 25 person on the basis of a reference fingerprint, comprising a memory, a processor (14) and a biometrics module (17) executable by the processor (14) for comparing comparison minutiae of the comparison fingerprint (23) with reference minutiae (19) of the reference fingerprint, wherein: 30 the memory is adapted to store the reference minutiae (19) of the reference fingerprint; and the biometrics module (17) is adapted to determining one baseline pair, at least a third pair of minutiae and as many as possible further pairs of minutiae, and to 5 evaluate the comparison fingerprint (23) of the person on the basis of the determined pairs of minutiae, wherein the baseline pair comprises two pairs of minutiae formed respectively by corresponding comparison minutiae and reference minutiae (19) and the third pair of minutiae comprises a comparison minutia and a corresponding reference minutia (19); 10 characterized in that the biometrics module (19) is furthermore adapted: to define on the basis of the determined pairs of minutiae a chain starting with the baseline pair, to add each determined pair of minutiae to the chain, wherein the chain 15 includes at least three determined pairs of minutiae and wherein the order of the pairs of minutiae in this chain is invariable in the further course of procedure, to determine three relation pairs of minutiae (A-A1, B-B', C-C, D-D') within the chain of all the determined pairs of minutia, to determine a further pair of minutiae on the basis of the three determined 20 relation pairs of minutiae by comparing geometrical relations between a selected reference minutia and the reference minutiae of the three pairs of relation minutiae with geometrical relations between a selected comparison minutia and the comparison minutiae of the three pairs of relation minutiae; and the memory is furthermore adapted to store the chain of the determined pairs 25 of minutiae. 20. Chip card (10) as claimed in claim 19, wherein as memory a nonvolatile memory (12) and/or a permanent memory (11) is used. 30 21. Chip card (10) as claimed in claim 19 or 20, wherein the biometrics module (17) is integrated in an operating system (16) residing in a permanent memory (11) of the chip card (10) or lies in a nonvolatile memory (12) or 5 is implemented as a biometric co-processor. 22. Chip card (10) as claimed in one of claims 19 to 21, wherein the biometrics module (17) is adapted to determine as relation pairs of minutiae the pairs of minutiae disposed in the first, the penultimate and the ultimate position of the chain. 10 23. Chip card (10) as claimed in one of claims 19 to 22, wherein the biometrics module (17) is adapted, when detennining the further pair of minutiae, to consider the distances of the minutiae of the further pair of minutiae to the corresponding minutiae of the relation pairs of minutiae in the relations. 15 24. Chip card (10) as claimed in one of claims 19 to 23, wherein the biometrics module (17) is adapted, when determining the further pair of minutiae, to consider the angles enclosed by the minutiae of the further pair of minutiae and the corresponding minutiae of the ultimate and the penultimate pair of minutiae of the chain in the rela- 20 tions. 25. Chip card (10) as claimed in one of claims 19 to 24, wherein the biometrics module (17) is adapted, when determining the further pair of minutiae, to compare the minutia angle of the comparison minutia of the further pair of minutiae with the minu- 25 tia angle of the reference minutia (19) of the further pair of minutiae. 26. Chip card (10) as claimed in claim 25, wherein the biometrics module (17) is adapted, when determining the further pair of minutiae, to compare the minutia angles first and to discontinue the determining, if these angles do not lie within a 30 predetermined tolerance range. 26 Amended 1 27. Chip card (10) as claimed in claim 26 with 23, wherein the biometrics module (17) is adapted, after comparing the minutia angles of the minutiae of the further pair of minutiae, to compare the distances of the minutiae of the further pair of minutiae 5 and to discontinue the determining, if these distances do not lie within predetermined tolerance ranges. 28. Chip card (10) as claimed in claim 26 or 27, wherein the biometrics module (17) is adapted, if the determining of the further pair of minutiae is discontinued, to 10 carry out this determining with a different comparison minutia and/or a different reference minutia (19) again. 29. Chip card (10) as claimed in one of claims 25 to 27, wherein the biometrics module (17) is adapted to sort the comparison minutiae in accordance with their 15 minutia angles before the comparison with the reference minutiae (19) takes place, and the chip card comprises a nonvolatile memory (12) adapted to store this sorting of the comparison minutiae. 30. Chip card (10) as claimed in one of claims 19 to 29, wherein the biometrics 20 module (17) is adapted to evaluate the comparison fingerprint (23) of the person, as soon as no further pair of minutiae can be determined. 31. Chip card (10) as claimed in one of claims 19 to 30, wherein the biometrics module (17) is adapted, when determining the further pair of minutiae, to calculate 25 angles anaVor distances of the reference minutiae (19) only when they are needed for comparison with angles and/or distances of the corresponding comparison minutiae. 32. Chip card (10) as claimed in claim 31, wherein the biometrics module (17) is adapted to store calculated angles and distances for further comparisons in a 30 nonvolatile memory (12). 33. Chip card (10) as claimed in one of claims 19 to 32, wherein the memory is adapted to store a predetermined sequence of reference minutiae with the reference minutiae (19), and the biometrics module (17) is adapted, when determining the 5 baseline pair and the further pairs of minutiae, to consider the reference minutiae (19) in the order predetermined by the sequence of reference minutiae. 34. Chip card (10) as claimed in claim 33, wherein the biometrics module (17) is adapted to carry on with the subsequent reference minutia (19) of the sequence, if no 10 pair of minutiae can be determined for a reference minutia (19) in the order determined by the sequence of reference minutiae. 35. Chip card (10) as claimed in 33 or 34, characterized in that the biometrics module (17) is adapted, when determining the baseline pair, to consider only such 15 reference minutiae (19) which follow each other directly in the sequence of reference minutiae. 36. Chip card (10) as claimed in one of claims 19 to 25, wherein the chip card (10) comprises a data communication interface (15), via which the comparison . 20 fingerprint (23) is received. 37. System for biometrically verifying a comparison fingerprint (23) of a person on the basis of a reference fingerprint, characterized by a chip card (10) as claimed in one of claims 19 to 36 and a verification device (20), wherein the verification device 25 (20) has a sensor (21) which is adapted to record the comparison fingerprint (23) of the person. 38. System as claimed in claim 37, wherein the verification device (20) has a data communication interface (22), which is adapted to correspond with the data 30 communication interface (15) of the chip card (10) and to transmit the comparison fingerprint (23) to the chip card (10). 5 10 ABSTRACT METHOD FOR BIOMETRJCALLY VERIFYING A COMPARISON FINGERPRINT OF A PERSON AND CHIP CARD THEREFOR The invention relates to a method for biometrically verifying a comparison fingerprint (23) of a person on the basis of a reference fingerprint stored on a chip card (10) by means of comparing comparison minutiae (A', B1, C, D, E', F1) of the comparison fingerprint (23) with reference minutiae (A, B, C, D, E, F) i of the reference fingerprint for the purpose of authenticating a person by the steps: determining a baseline pair (A-B/A'-B'), consisting of two pairs of minutiae (A-A\ B-B') formed respectively by comparison minutiae (A', B') and reference minutiae (A, B) respectively corresponding to each other; determining third pairs of minutia formed respectively by comparison minutiae (C, D') and reference minutiae (C, D) respectively corresponding to each other ; determining as many as possible further pairs of minutiae of comparison minutiae (E1) and reference minutiae (E) respectively corresponding to each other; evaluating the comparison fingerprint of the person on the basis of the determined pairs of minutiae, wherein a person is regarded as authenticated, if the number of detected pairs of minutiae exceeds a predetermined threshold value ; wherein the determined pairs of minutiae define a chain starting with the pairs of minutiae (A-A', B-B') of the baseline pair (A-A\ B-B'), to which chain every determined pair of minutiae (C-C, D-D') is added, wherein the chain comprises at least three determined pairs of minutiae and wherein the order of the pairs of minutiae in this chain is invariable in the further course of procedure ; three relation pairs of minutiae (A-A', B-Br, C-C, D-Dr) are determined within the chain of all the determined pairs of minutia and that a further pair of minutiae (E-E1) is determined on the basis of the three determined relation pairs of minutiae by comparing geometrical relations between a selected reference minutia and the reference minutiae of the three pairs of relation minutiae with geometrical relations between a selected comparison minutia and the comparison minutiae of the three pairs of relation minutiae. The invention also discloses a chip card (10) for biometrically verifying a comparison fingerprint (23) of a person on the basis of a reference fingerprint.

Documents:

03576-kolnp-2007-abstract.pdf

03576-kolnp-2007-claims.pdf

03576-kolnp-2007-correspondence others.pdf

03576-kolnp-2007-description complete.pdf

03576-kolnp-2007-drawings.pdf

03576-kolnp-2007-form 1.pdf

03576-kolnp-2007-form 3.pdf

03576-kolnp-2007-form 5.pdf

03576-kolnp-2007-gpa.pdf

03576-kolnp-2007-international publication.pdf

03576-kolnp-2007-pct priority document notification.pdf

03576-kolnp-2007-pct request form.pdf

3576-KOLNP-2007-(02-07-2014)-ANNEXURE TO FORM 3.pdf

3576-KOLNP-2007-(02-07-2014)-CORRESPONDENCE.pdf

3576-KOLNP-2007-(02-07-2014)-OTHERS.pdf

3576-KOLNP-2007-(07-07-2014)-ABSTRACT.pdf

3576-KOLNP-2007-(07-07-2014)-CLAIMS.pdf

3576-KOLNP-2007-(07-07-2014)-CORRESPONDENCE.pdf

3576-KOLNP-2007-(07-07-2014)-DESCRIPTION (COMPLETE).pdf

3576-KOLNP-2007-(07-07-2014)-DRAWINGS.pdf

3576-KOLNP-2007-(07-07-2014)-FORM-1.pdf

3576-KOLNP-2007-(07-07-2014)-FORM-2.pdf

3576-KOLNP-2007-(07-07-2014)-FORM-3.pdf

3576-KOLNP-2007-(07-07-2014)-FORM-5.pdf

3576-KOLNP-2007-(07-07-2014)-PA.pdf

3576-KOLNP-2007-(07-07-2014)-PETITION UNDER RULE 137.pdf

3576-KOLNP-2007-(11-09-2014)-CORRESPONDENCE.pdf

3576-KOLNP-2007-(29-12-2014)-CORRESPONDENCE.pdf

3576-KOLNP-2007-ASSIGNMENT-1.1.pdf

3576-KOLNP-2007-ASSIGNMENT.pdf

3576-KOLNP-2007-CORRESPONDENCE.pdf

3576-KOLNP-2007-EXAMINATION REPORT.pdf

3576-KOLNP-2007-FORM 18-1.1.pdf

3576-kolnp-2007-form 18.pdf

3576-KOLNP-2007-GPA.pdf

3576-KOLNP-2007-GRANTED-ABSTRACT.pdf

3576-KOLNP-2007-GRANTED-CLAIMS.pdf

3576-KOLNP-2007-GRANTED-DESCRIPTION (COMPLETE).pdf

3576-KOLNP-2007-GRANTED-DRAWINGS.pdf

3576-KOLNP-2007-GRANTED-FORM 1.pdf

3576-KOLNP-2007-GRANTED-FORM 2.pdf

3576-KOLNP-2007-GRANTED-FORM 3.pdf

3576-KOLNP-2007-GRANTED-FORM 5.pdf

3576-KOLNP-2007-GRANTED-SPECIFICATION-COMPLETE.pdf

3576-KOLNP-2007-INTERNATIONAL PUBLICATION.pdf

3576-KOLNP-2007-PETITION UNDER RULE 137.pdf

3576-KOLNP-2007-REPLY TO EXAMINATION REPORT.pdf

3576-KOLNP-2007-TRANSLATED COPY OF PRIORITY DOCUMENT.pdf

abstract-03576-kolnp-2007.jpg