KR102747700B1 - Device and method for generating cancellable fingerprint template based on delauney triangulation using a feature that is robust against rotation - Google Patents

Abstract

A device and method for generating a Dollone-based replaceable fingerprint template using a rotation-resistant feature are disclosed. The replaceable fingerprint template generating device includes a minusia extraction unit for extracting a plurality of minusiae from a fingerprint image, a Dollone triangulation unit for generating a plurality of Dollone triangles by performing Dollone triangulation using the extracted minusiae, a feature vector generation unit for generating a plurality of feature vectors each corresponding to each of the plurality of Dollone triangles, and a fingerprint template generation unit for generating at least one dummy feature vector and generating a fingerprint template including the at least one dummy feature vector and the plurality of feature vectors.

Description

{DEVICE AND METHOD FOR GENERATING CANCELLABLE FINGERPRINT TEMPLATE BASED ON DELAUNEY TRIANGULATION USING A FEATURE THAT IS ROBUST AGAINST ROTATION}

The present invention relates to a device and method for generating a replaceable fingerprint template based on a dolomite using a rotation-resistant characteristic.

Recently, in our society, due to the increase in the connection between online and offline and the increase in non-face-to-face online activities, there has been an increase in cases where personal information and online activities are threatened by exposing and stealing personal information. Accordingly, the need for secure personal information protection and authentication is emerging.

Currently widely used authentication methods include passwords, PINs (Personal Identification Numbers), seals, and signatures, but these do not provide high security due to forgetting, loss, forgery, and theft. On the other hand, biometric authentication uses the user's unique biometric information, and provides high security performance without concerns about loss or theft.

Biometric authentication uses body features, and there are various authentication methods using fingerprints, irises, veins, etc. By utilizing these technologies, safer and more convenient authentication services are being provided in the telecommunications, finance, medical, and public sectors.

Biometric authentication is a technology that is gaining attention because it is convenient and has high security, but it also has vulnerabilities. Passwords, PINs, and signatures that were widely used in the past can be changed if they are exposed to danger. However, biometric information is unique information and has an immutable nature. Therefore, if biometric information is stolen or hacked, it cannot be reissued or changed. For this reason, safe storage and management of biometric information is even more important.

The technical problem to be achieved by the present invention is to provide a device and method for generating a replaceable fingerprint template based on a dolomite using a rotation-resistant characteristic.

A fingerprint template generating device according to one embodiment of the present invention includes a minusia extraction unit that extracts a plurality of minusiae from a fingerprint image, a Dolone triangulation unit that generates a plurality of Dolone triangles by performing Dolone triangulation using the extracted minusiae, a feature vector generation unit that generates a plurality of feature vectors each corresponding to each of the plurality of Dolone triangles, and a fingerprint template generation unit that generates at least one dummy feature vector and generates a fingerprint template including the at least one dummy feature vector and the plurality of feature vectors.

A fingerprint template generation method according to one embodiment of the present invention is performed by a computing device including at least a processor, and includes the steps of extracting a plurality of minutiae from a fingerprint image, performing Dollone triangulation using the extracted minutiae to generate a plurality of Dollone triangles, generating a plurality of feature vectors, each feature vector corresponding to a respective one of the plurality of Dollone triangles, and generating at least one dummy feature vector and generating a fingerprint template including the at least one dummy feature vector and the plurality of feature vectors.

In the case of a fingerprint template generation device and method according to an embodiment of the present invention, there is an effect of being able to generate a fingerprint template by utilizing a rotation-resistant feature.

In addition, by including dummy feature vectors in the fingerprint template, it is possible to prevent privacy invasion problems caused by fingerprint template leakage.

In order to more fully understand the drawings cited in the detailed description of the present invention, a detailed description of each drawing is provided.
Figure 1 is a drawing for explaining a feature vector used in the present invention.
Figure 2 is a graph for explaining the experimental results of the present invention.
FIG. 3 is a functional block diagram of a fingerprint template generation device according to one embodiment of the present invention.
FIG. 4 is a flowchart for explaining a fingerprint template generation method performed by the fingerprint template generation device illustrated in FIG. 1.

Specific structural or functional descriptions of embodiments according to the concept of the present invention disclosed in this specification are merely exemplified for the purpose of explaining embodiments according to the concept of the present invention, and embodiments according to the concept of the present invention can be implemented in various forms and are not limited to the embodiments described in this specification.

Since embodiments according to the concept of the present invention can have various changes and can have various forms, the embodiments are illustrated in the drawings and described in detail in this specification. However, this is not intended to limit the embodiments according to the concept of the present invention to specific disclosed forms, but includes all modifications, equivalents, or substitutes included in the spirit and technical scope of the present invention.

The terms first or second, etc. may be used to describe various components, but the components should not be limited by the terms. The terms are only intended to distinguish one component from another, for example, without departing from the scope of the invention, a first component may be referred to as a second component, and similarly, a second component may also be referred to as a first component.

When it is said that a component is "connected" or "connected" to another component, it should be understood that it may be directly connected or connected to that other component, but that there may be other components in between. On the other hand, when it is said that a component is "directly connected" or "directly connected" to another component, it should be understood that there are no other components in between. Other expressions that describe the relationship between components, such as "between" and "directly between" or "adjacent to" and "directly adjacent to", should be interpreted similarly.

The terminology used herein is only used to describe particular embodiments and is not intended to be limiting of the present invention. The singular expression includes the plural expression unless the context clearly indicates otherwise. It should be understood that, as used herein, the terms "comprises" or "has" and the like are intended to specify the presence of a feature, number, step, operation, component, part, or combination thereof described in the present specification, but do not exclude in advance the possibility of the presence or addition of one or more other features, numbers, steps, operations, components, parts, or combinations thereof.

Unless otherwise defined, all terms used herein, including technical or scientific terms, have the same meaning as commonly understood by one of ordinary skill in the art to which this invention belongs. Terms defined in commonly used dictionaries, such as those defined in common usage, should be interpreted as having a meaning consistent with the meaning they have in the context of the relevant art, and will not be interpreted in an idealized or overly formal sense unless explicitly defined herein.

Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings attached to this specification. However, the scope of the patent application is not limited or restricted by these embodiments. The same reference numerals presented in each drawing represent the same components.

A replaceable biometric template applies a one-way transformation function to the original biometric information so that the original biometric information cannot be known from the transformed template. This technology makes it impossible for any attacker to reconstruct the information of the original data from the transformed biometric data even if they obtain it. The concept of replaceable biometric templates was first proposed by Ratha et al. in 2001 (Ratha, N.K., Connell, J.H., Bolle, R.M., Enhancing security and privacy in biometrics-based authentication systems. IBM Syst. J. 40 (3), 614-634. 2001.). In 2006, Cartesian, Radial, and Functional transformations were proposed as replaceable biometric template transformations (Ratha, N.K., Connell. J.H, Bolle, R.M., Chikkerur, S., Cancelable biometrics: A case study in fingerprints. International Conference on Pattern Recognition (ICPR), vol. 4, pp. 370-373, 2006.).

In addition, Dolone triangulation has been widely used as a feature value that is not greatly affected by the distortion or rotation of the fingerprint minusia. Bebis et al. showed that Dolone triangulation has a property that does not change greatly by the addition or deletion of noise or minusia (Bebis, G. , Deaconu, T. , Georgiopoulos, M. Fingerprint identification using delaunay triangulation. In: International Conference on Information Intelligence and Systems. IEEE, pp. 452-459 .1999.). In general, when looking at several images generated from the same fingerprint, it can be seen that the locations of the minusia are extracted slightly differently overall. If Dolone triangulation is applied to the minusia, these changes can be easily adjusted and used.

In this regard, Sandhya, Prasad, Yang et al. recently proposed a delaunay-based replaceable template technique in 2015 and 2013 (Sandhya, M., Prasad, M.V.N.K., Chillarige, R.R. Generating cancellable finger-print templates based on delaunay triangle feature set construction. IET Biomet. 5 (2), 131-139. doi:10.1049/iet-bmt.2015.0034., 2016., Yang, W., Hu, J., Wang, S., Yang, J., Cancelable fingerprint templates with delaunay triangle-based local structures. Cyberspace Safety and Security. Springer, pp. 81-91, 2013.). In 2020, Trivedi et al. proposed a Dolonne-based replaceable template technique (Amit Kumar Trivedi, Dalton Meitei Thounaojama, Shyamosree Pal, Non-Invertible cancellable fingerprint template for fingerprint biometric, Elsevier Ltd, 2020.). However, the possibility of rotation of the fingerprint template was not properly considered before conducting the experiment, and the directionality of the minusia, which is an absolute value rather than a relative value from the triangle, was used, which was greatly affected by the fingerprint rotation. In addition, since it is a method using singular points, there is a vulnerability that there is a difference in singular points depending on the clarity of the image file when comparing fingerprints of the same person.

Hereinafter, a fingerprint template generation method according to one embodiment of the present invention is described. In this case, a more accurate template generation method can be provided by using the relative features of triangles in the Dolone triangle of the Minusia point.

In order to protect the information of the original fingerprint template, n relative matching feature values (n is any natural number, an exemplary value may be 16. In addition, the matching feature values may be named a feature vector) may be arbitrarily selected (or generated) and a fingerprint template including the same may be generated. The additional matching feature values may serve as a user's secret key.

To do this, first, the minutia points are extracted from the fingerprint (or fingerprint image). Then, the minutia points extracted from the fingerprint are used to create a Dolone triangle. Here, relative values are used to accurately match genuine even for different templates of the same fingerprint.

The vector for fingerprint template matching (which may be named a matching vector or a feature vector) is as shown in the mathematical expression 1 below. In addition, with respect to the configuration of the feature vector, reference may be made to FIG. 1.

[Mathematical formula 1]

In mathematical expression 1, refers to the feature vector of the i-th triangle among the Dolone triangles extracted from the user's fingerprint, It means the largest angle among the interior angles of the Dolone triangle, It means the smallest angle among the interior angles of the Dolone triangle, It means the length of the longest side among the sides of the Dolone triangle, It refers to the radius of the circumcircle passing through the three vertices of the Dolone triangle. is the largest cabinet The vertex of Any one of the remaining vertices in Vector to ( )and Another vertex in Vector to ( ) of the outer value ( ) can mean a value that can identify the sign of the symbol. For example, It can have a value of 0 if the outer product is negative, and a value of 1 if the outer product is positive. is the largest interior angle of a Dolone triangle. The vertex of The direction vector of the corresponding minusia and It can mean the angle between vectors connecting adjacent edges, for example, edges of medium size.

The above-described feature vector includes six features. However, the present invention is not limited to the number of features included in the feature vector, and it can be understood that the feature vector includes at least one feature. In addition, since the feature vector corresponds to the Dolone triangle extracted from the fingerprint, the number of feature vectors corresponding to one fingerprint template can be equal to the number of Dolone triangles.

Afterwards, a fingerprint template can be generated that includes the previously described random feature vector (which may be named a dummy feature vector as a feature vector generated using random values) and the feature vectors extracted from the fingerprint.

As described above, matching can be performed using the six relative values of the Dolone triangle. In the matching process, if a similar feature vector is found by passing the threshold, the Count is increased. The final comparison value matching score can be calculated by dividing the Count value (or the square of the Count) by the product of the number of feature vectors of the two fingerprints (N _T , N _Q ). This can be expressed by mathematical formula 2.

[Mathematical formula 2]

If the matching score value is greater than (or equal to or greater than) a predetermined threshold, the two fingerprints to be compared can be determined to be fingerprints of the same person, and if the matching score value is less than (or equal to or less than) the predetermined threshold, the two fingerprints to be compared can be determined not to be fingerprints of the same person.

In other words, the matching score can be calculated based on the number of matching feature vectors. That is, the matching score is the number of matching feature vectors divided by the sum of the number of feature vectors (or the square of the number) included in the fingerprint template to be compared and the number of feature vectors included in the pre-stored fingerprint template.

Below, the experimental results are described.

In the experiment of the present invention, in addition to the fingerprint data FVC2002 DB1 and DB2 used in the paper by Trivedi et al., FVC2002 DB3 and DB4 were used.

The matching process using the six relative values of the Dolone triangle involves the angle The threshold value in is 10, length The experiment was conducted by setting the threshold value to 15. Genuine matching performed a comparison operation between fingerprint images of the same person (28×100=2800 comparisons), and Impostor matching performed a comparison operation between the first fingerprint of each person and the first fingerprint of another person (99+98+…+2+1=4950 comparisons).

The experimental results in Fig. 2 are graphs showing FAR and FRR when matching using relative feature values in the Dolone triangle of the Minusia point according to the technique proposed in this specification.

FRR(False Reject Rate) is the probability that a fingerprint template that should be matched with the same fingerprint fails to match, and FAR(False Accept Rate) is the probability that a matching succeeds when comparing fingerprint templates from different people. The value of the intersection of FRR and FAR in the graph represents ERR(Equal Error Rate). ERR is the point where the error probabilities of FAR and FRR become the same. Therefore, this value can be seen as a measure of efficiency and accuracy in the biometric authentication process.

Therefore, as shown in Table 1, the ERR of this experiment was found to be smaller than that of the previous study by Trivedi et al., showing better performance.

[Table 1]

FIG. 3 is a functional block diagram of a fingerprint template generation device according to one embodiment of the present invention.

Referring to FIG. 3, the fingerprint template generation device (100) may include at least one of a minusia extraction unit (110), a Dolone triangulation unit (120), a feature vector generation unit (130), a fingerprint template generation unit (140), a matching unit (150), and a storage unit (160). For example, the fingerprint template generation unit (100) may be configured to include a matching unit (150) to determine whether or not a fingerprint template to be compared matches (or is authenticated). In this case, the fingerprint template generation device (100) may also be named a fingerprint authentication device, a fingerprint recognition device, a fingerprint matching device, etc.

Additionally, the fingerprint template generation device (100) may be implemented as a computing device including at least a processor and/or a memory. The computing device may include a desktop PC, a server, a tablet PC, a handheld device, a wearable device, a smart phone, an HMD, a navigation device, etc.

A minusia extraction unit (110) can extract a minusia (or minusia point) from a fingerprint (or fingerprint image). Since the method of extracting a minusia from a fingerprint is widely known, a detailed description thereof will be omitted.

The fingerprint may be scanned by a user's fingerprint using a predetermined input device, or may be scanned by an external device and then received via a wired or wireless communication network. The fingerprint may be received in advance as described above and stored in the storage unit (160).

The Dolone triangulation unit (120) performs Dolone triangulation using the extracted minusiae and can generate multiple Dolone triangles. Since the Dolone triangulation operation is widely known, a detailed description thereof will be omitted.

The feature vector generation unit (130) can generate a plurality of feature vectors corresponding to each of the generated Dolone triangles. The number of feature vectors generated by the feature vector generation unit (130) may be equal to the number of Dolone triangles, but the present invention is not limited thereto.

The fingerprint template generation unit (140) can generate at least one feature vector having an arbitrary value, that is, at least one dummy feature vector, and generate a fingerprint template including the dummy feature vector and the feature vectors generated by the feature vector generation unit (130). The generated fingerprint template corresponds to a fingerprint, and even fingerprints of the same person can have different values depending on the fingerprint image or the dummy feature vector added.

The matching unit (150) can determine whether a fingerprint template to be compared matches with fingerprint templates that are stored in advance. Specifically, the matching unit (150) can determine whether a fingerprint template to be compared (e.g., a fingerprint template generated by the fingerprint template generating unit (140)) matches with at least one of the fingerprint templates that are stored in advance.

In order to match, it can be determined whether each feature vector included in the fingerprint template to be compared matches any one of the feature vectors included in at least one fingerprint template. Whether or not it matches can be determined based on a matching score. That is, it can be determined whether or not the fingerprint template to be compared matches any one of the fingerprint templates stored in advance based on a predetermined reference value. Matching the fingerprint templates can mean that they are fingerprint templates generated from the fingerprint of the same person.

Depending on the embodiment, the fingerprint template to be compared may not include a dummy feature vector. That is, when performing an authentication operation, etc., a higher effect may be obtained by not including a dummy feature vector in the fingerprint template to be authenticated.

In the storage unit (160), a plurality of fingerprints including the user's fingerprint, a plurality of fingerprint templates including the user's fingerprint template, Minusia points, Dolone triangles, feature vectors, etc. extracted from each fingerprint can be temporarily or non-temporarily stored.

FIG. 4 is a flow chart for explaining a fingerprint template generation method performed by the fingerprint template generation device illustrated in FIG. 3. When explaining a fingerprint template generation method or a user authentication (recognition, matching) method using a fingerprint template, description of the same content as described above will be omitted. In addition, at least some of the operations of the methods below may be understood as operations of a processor constituting the fingerprint template generation device (100).

Referring to FIGS. 3 and 4, a minusiae can be extracted from a fingerprint (or fingerprint image) (S110). The minusiae extraction operation can be performed by a minusiae extraction unit (110) of a fingerprint template generation device (100).

The Dolone triangulation unit (120) of the fingerprint template generation device (100) can generate a plurality of Dolone triangles using the extracted minusia (S120).

Thereafter, the feature vector generation unit (130) of the fingerprint template generation device (100) can generate a feature vector for each of the generated Dolone triangles (S130). That is, each of the plurality of feature vectors corresponds to one of the plurality of Dolone triangles.

The fingerprint template generation unit (140) of the fingerprint template generation device (100) can generate a fingerprint template including generated feature vectors and dummy feature vectors (S140).

In addition, the matching unit (150) of the fingerprint template generation device (100) can determine whether there is a match by comparing the fingerprint template to be compared with at least one fingerprint template among the fingerprint templates stored in advance (S150).

The devices described above may be implemented as hardware components, software components, and/or a collection of hardware components and software components. For example, the devices and components described in the embodiments may be implemented using one or more general-purpose computers or special-purpose computers, such as, for example, a processor, a controller, an arithmetic logic unit (ALU), a digital signal processor, a microcomputer, a field programmable array (FPA), a programmable logic unit (PLU), a microprocessor, or any other device capable of executing instructions and responding. The processing device may execute an operating system (OS) and one or more software applications running on the operating system. In addition, the processing device may access, store, manipulate, process, and generate data in response to the execution of the software. For ease of understanding, the processing device is sometimes described as being used alone, but those skilled in the art will appreciate that the processing device may include multiple processing elements and/or multiple types of processing elements. For example, the processing unit may include multiple processors, or a processor and a controller. Other processing configurations, such as a parallel processor, are also possible.

The software may include a computer program, code, instructions, or a combination of one or more of these, and may configure a processing device to perform a desired operation or may independently or collectively command the processing device. The software and/or data may be permanently or temporarily embodied in any type of machine, component, physical device, virtual equipment, computer storage medium or device, or transmitted signal wave to be interpreted by the processing device or to provide instructions or data to the processing device. The software may be distributed on network-connected computer systems and stored or executed in a distributed manner. The software and data may be stored in one or more computer-readable recording media.

The method according to the embodiment may be implemented in the form of program commands that can be executed through various computer means and recorded on a computer-readable medium. The computer-readable medium may include program commands, data files, data structures, etc., alone or in combination. The program commands recorded on the medium may be those specially designed and configured for the embodiment or may be those known to and usable by those skilled in the art of computer software. Examples of the computer-readable recording medium include magnetic media such as hard disks, floppy disks, and magnetic tapes, optical media such as CD-ROMs and DVDs, magneto-optical media such as floptical disks, and hardware devices specially configured to store and execute program commands such as ROMs, RAMs, flash memories, etc. Examples of the program commands include not only machine language codes generated by a compiler but also high-level language codes that can be executed by a computer using an interpreter, etc. The hardware devices described above may be configured to operate as one or more software modules to perform the operations of the embodiment, and vice versa.

Although the present invention has been described with reference to the embodiments illustrated in the drawings, this is merely exemplary, and those skilled in the art will understand that various modifications and equivalent other embodiments are possible therefrom. For example, appropriate results can be achieved even if the described techniques are performed in a different order than the described method, and/or components of the described systems, structures, devices, circuits, etc. are combined or combined in a different form than the described method, or are replaced or substituted by other components or equivalents. Accordingly, the true technical protection scope of the present invention should be defined by the technical spirit of the appended claims.

100 : Fingerprint template generation device
110: Minusia Extraction Department
120: Dolone triangle
130: Feature vector generation section
140: Fingerprint template generation section
150 : Matching section
160 : Storage

Claims (10)

A minusia extraction unit for extracting multiple minusiae from a fingerprint image;
A Dolone triangulation unit that generates multiple Dolone triangles by performing Dolone triangulation using the extracted minuscules;
A feature vector generation unit for generating a plurality of feature vectors, each of which corresponds to each of the plurality of Dolone triangles; and
A fingerprint template generation unit comprising: a fingerprint template generation unit generating at least one dummy feature vector and generating a fingerprint template including the at least one dummy feature vector and the plurality of feature vectors;
The above feature vector generation unit generates a feature vector expressed by mathematical formula 1,
Mathematical expression 1 is And,
Above refers to the feature vector of the i-th Dolone triangle among the Dolone triangles extracted from the above fingerprint,
Above means the largest angle among the interior angles of the i-th Dolone triangle,
Above means the smallest angle among the interior angles of the i-th Dolone triangle,
Above means the length of the longest side among the sides of the i-th Dolone triangle,
Above denotes the radius of the circumscribed circle passing through the three vertices of the i-th Dolone triangle,
Above Silver is above The vertex of ( ) among the remaining vertices ( ) to the vector ( ) and the above Another vertex in ( ) to the vector ( ) of the outer value ( ) means a value that can identify the sign of
Above is above The direction vector of the corresponding minus and the above It means the angle between the vectors connecting one of the adjacent sides in .
Fingerprint template generator. delete delete In the first paragraph,
Above The vertex of ( ) among the remaining vertices ( ) to the vector ( ) and the above Another vertex in ( ) to the vector ( ) of the outer value ( ) if the sign is (-). The value of is either 0 or 1,
Above The vertex of ( ) among the remaining vertices ( ) to the vector ( ) and the above Another vertex in ( ) to the vector ( ) of the outer value ( ) if the sign is (+). The value of is either 0 or 1,
Fingerprint template generator. In the first paragraph,
The fingerprint template generation device further includes a matching unit that determines whether the fingerprint template matches a plurality of fingerprint templates stored in advance.
Fingerprint template generator. A method for generating a fingerprint template performed by a computing device including at least a processor,
A step of extracting multiple minuscules from a fingerprint image;
A step of generating multiple Dolone triangles by performing Dolone triangulation using the extracted minuscules;
a step of generating a plurality of feature vectors, each of which corresponds to each of the plurality of Dolone triangles; and
A step of generating at least one dummy feature vector, and generating a fingerprint template including the at least one dummy feature vector and the plurality of feature vectors,
The step of generating the above feature vectors generates a feature vector expressed by mathematical formula 1,
Mathematical expression 1 is And,
Above refers to the feature vector of the i-th Dolone triangle among the Dolone triangles extracted from the above fingerprint,
Above means the largest angle among the interior angles of the i-th Dolone triangle,
Above means the smallest angle among the interior angles of the i-th Dolone triangle,
Above means the length of the longest side among the sides of the i-th Dolone triangle,
Above denotes the radius of the circumscribed circle passing through the three vertices of the i-th Dolone triangle,
Above Silver is above The vertex of ( ) among the remaining vertices ( ) to the vector ( ) and the above Another vertex in ( ) to the vector ( ) of the outer value ( ) means a value that can identify the sign of
Above is above The direction vector of the corresponding minus and the above It means the angle between the vectors connecting one of the adjacent sides in .
How to create a fingerprint template. delete delete In Article 6,
Above The vertex of ( ) among the remaining vertices ( ) to the vector ( ) and the above Another vertex in ( ) to the vector ( ) of the outer value ( ) if the sign is (-). The value of is either 0 or 1,
Above The vertex of ( ) among the remaining vertices ( ) to the vector ( ) and the above Another vertex in ( ) to the vector ( ) of the outer value ( ) if the sign is (+). The value of is either 0 or 1,
How to create a fingerprint template. In Article 6,
The above fingerprint template generation method further includes a step of determining whether the fingerprint template matches a plurality of fingerprint templates stored in advance.
How to create a fingerprint template.

Images