A Study of Fingerprint Biometric Templates by Using Delaunay Based Structures

A Study of Fingerprint Biometric Templates by Using Delaunay Based Structures

Suganya. A1, Mary Amirtha Sagayee. G2

PG Student1, Department of Electronics and Communication Engineering, Parisutham Institute of Technology and Science, Thanjavur, Tamilnadu, India.

Professor2, Department of Electronics and Communication Engineering, Parisutham Institute of Technology and Science, Thanjavur, Tamilnadu, India.

Abstract- A fingerprint based authentication is one of mature and reliable biometric recognition techniques owning to the distinctiveness and stability that fingerprints can provide compared to other biometrics. The method of fingerprint authentication system can be divided into two types: Texture- based and Minutiae based methods. Compare to texture- based, minutiae based methods are more reliable and unique. Although much attention has been given to minutiae based matching, during fingerprint image acquisition uncertainty of fingerprint caused by non linear deformation, rotation and translation. In order to reduce fingerprint uncertainty and improve the system recognition, this paper presents a complete review of existing Delaunay based structures for authentication. A Delaunay is numerous algorithms for computing triangulation.

Keywords- Fingerprints, Biometrics, Delaunay Triangulation, Delaunay Quadrangle, Delaunay Pentangle.

1. INTRODUCTION

   1. Biometrics

      Biometric is an automated methodology to uniquely identify human based on their physiological and behavioural characteristics. Many biometric characteristics have been proposed for authentication purpose. Consistently, biometric method can be pronounced into two types: behavioural-based method and physiological based method.

      In behavioural based method perform task of authentication based on human behavioural Characteristics. The major issue with behavioural based method is not unique, they all have more variation, cannot cope with and difficult to measure because of influences such as stress, thrust or stain. But the Implementation of behavioural based method less cost.

      Physiological-based method perform authentication by means of his and her physiological characteristics. The advantages of the physiological based method are more stable and more invasiveness and rare hacking only than behavioural based method.

   2. Fingerprints

   In the world of biometrics one of the most invasiveness and mature biometric recognition owning to the more Distinctiveness and stability that using fingerprint based authentication can provide better performance compare to other method. Fingerprint biometrics method can be classified into two types are texture and ridge feature

   based, method compare to texture based, ridge feature based method has more social acceptability and more reliable. Fingerprint identification system represents fingerprints in terms of their feature points. The two popular eminent minutiae points are termination and ridge bifurcation. Once the minutiae points are extracted from fingerprints and then Delaunay pentangle structures can be generated from feature points easily.

2. RELATED WORK

   The recent developments in fingerprint biometric recognition of a person lead to enhancements in accuracy and stability. The related work of Delaunay based structures for fingerprint recognition technologies analyzed with various parameters such as matching and recognition. In Abellanas et.al.[2] introduce a Delaunay triangle based structure for fingerprint using similar minutiae structures. The Delaunay triangle based structure has proved some excellent Characteristics. Firstly, it provides excellent structural stability under random positional disruptions each minutia likely to maintain a similar structure with its neighbouring minutiae under translation, rotation and small scale change because of nonlinear distortion. Secondly Delaunay triangulation is influenced locally by virtue of missing and spurious minutiae. This means that by reason of random positional disturbances, some part of Delaunay triangulation can still maintain structural stability.

   In [3] Bebies et al. proposed indexed based approach and Delaunay triangulation. The indexed based approach for fingerprint identification and Delaunay triangulation for extracting unique topology code. The leading demerit of this approach is local structures changed in presence of noise or distortion. In [4] Niel and Parziale proposed a redial basis function that applies to minutiae point set to forming a Delaunay triangulation and utilized several translation unchanged features and rotation of each and every Delaunay triangle to perform matching between template and quire images. In [5] Amirani et al. combined both Delaunay triangulation and voronoi diagram to generate hybrid matching algorithm.

   1. Delaunay Triangle-based Fingerprint Authentication System.

      A Delaunay triangle-based fingerprint recognition system can operate in either identification or verification mode. Fingerprint identification scheme, the comparison

      is done against templates corresponding to all the enrolled users in order to recognize the individual (a one-to-many matching). It is must be accurate. The general block diagram of Delaunay triangle based fingerprint authentication system is shown in figure [1].

      Database

      Fingerprint

      image

      Pre

      processing

      Minutiae

      Extraction

      Delaunay Triangle Matching

      Fingerprint

      image

      Pre

      processing

      Minutiae

      Extraction

      Delaunay Triangle Matching

      Accept Or Reject

      Fig. 1. Block diagram of Delaunay Triangle based fingerprint authentication system.

      Delaunay triangle based fingerprint biometric system perform authentication using similar triangulation. If Delaunay triangle based structures

      is less than threshold the person authorized otherwise unauthorized.

      1. Background on Delaunay Triangulation

         Triangulation is a process that takes a region of space and divides it into sub regions. The space may be of any dimension, however, a 2D space is considered because here, we are dealing with 2D Minutiae points. In this case, the sub regions are just triangles. Delaunay triangulations are build upon the construction given below briefly. A Delaunay triangle-based structure has a good structural stability in presence of random positional disruptions and each minutiae maintain similar structure.

         Given a set S of points s1, s2,sN, We can compute the Delaunay triangulation of S by first computing its voronoi diagram. The voronoi diagram decomposes the 2D space into regions around each minutiae point such that all the points in the region around si are closer to si than they are to any other point in S. After found the voronoi diagram, the Delaunay triangulation can be formed by connecting the center of every pair of neighbouring voronoi regions. Figure 2a shows a set of 2D minutiae points with thinned ridges, their voronoi diagram (thin line) and Delaunay triangulation (bold line) is shown in figure 2b.

         Fig. 2. (a) Set of minutiae points, (b) Voronoi diagram and their Delaunay triangulation.

         The Delaunay triangulation has certain properties, including: (1) the Delaunay triangulation of non-degenerate set of points is unique, (2) a circle through the three points of Delaunay triangle contain no other points and (3) the minimum angle across all the angles in all the triangles in a delaunay triangulation is greater than the minimum angle in any other triangulation of the same points.

         The fingerprint uncertainty caused one of the reasons of nonlnear distortion. Because of that neighbouring minutia, orientation between each minutiae and relative position changed. The Delaunay triangle based structures (EER= 4.02%, FAR= 2.23%, FRR= 5.7%) Telerate only rotation, translation but it suffered by in presence of non linear deformation.

   2. Delaunay Quadrangle based fingerprint authentication system

      Delaunay quadrangles are built upon the construction of the Delaunay triangulation net. The algorithm for producing Delaunay triangulation is detailed in [8]. Here we given a set of minutiae M = {mi}iN=1, Where N is a set of minutiae, as showed in figure 3. In order to construct Delaunay triangulation, first need to construct voronoi diagram. The job of voronoi diagram split local region into small cell based on minutiae points is there in images. All the points in the cell around mi or closure to mi than to any other minutiae. After that the Delaunay triangulation is formed by joining the centre of every pair of neighbouring in voronoi region. Next Delaunay quadrangle can be formed by combining any two Delaunay triangles that share a common side. The general block diagram of Delaunay quadrangle based fingerprint authentication system is shown in figure 4. In this case both template and query Delaunay quadrangle based structure similar the person authorized or unauthorized.

      Fig. 3. (a) set of minutiae point with thinned ridges and (b) delaunay quadrangle based structure.

      Database

      Fingerprint

      image

      Pre

      processing

      Minutiae

      Extraction

      Delaunay Quadrangle Matching

      Fingerprint

      image

      Pre

      processing

      Minutiae

      Extraction

      Delaunay Quadrangle Matching

      Accept Or Reject

      Fig. 4. Block diagram of Delaunay Quadrangle based fingerprint authentication system.

      Feature vector extracted from Delaunay pentangle based structure is of fixed length and alignment free. Generally speaking feature vector extracted from Delaunay quadrangle based structures are more discriminative and more attributes (EER= 1.68%, FAR=2.23% and FRR= 1.07%) than those Delaunay triangle based structures. The main advantage of Delaunay quadrangle based structure can tolerate local structural changed in presence of nonlinear distortion. But it has only less attributes than Delaunay pentangle based structures.

   3. Delaunay pentangle based fingerprint authentication system

      The delaunay pentangle based structure has more attributes and more discriminative ability to nonlinear distortion than delaunay quadrangle based structures. Feature vector extracted from delaunay pentangle is of fixed length and alignment free, which is less sensitive to nonlinear distortion. The delaunay pentangle based structures able to withstand local structural change in presence of nonlinear distortion. A delaunay pentangle based structure extracted from input fingerprint image in local region. Delaunay pentangle based structures avoid this global image registration because only local registration is needed by using local minutiae information. Both template and query delaunay pentangle based structure match the person authorized or unauthorized. In figure 6 shows on block diagram of delaunay pentangle based structure(EER=1.05%, FAR= 0 and FRR= 2.14%).

      Delaunay pentangle is built upon the construction of Delaunay triangulation net. The algorithm for producing Delaunay triangulation is detailed in [8]. Here we given a set of minutiae M = {mi}iN=1, Where N is a set of minutiae, as showed in figure 5.

      Fig. 5. Delaunay pentangle based structure

      In order to construct Delaunay triangulation, first need to construct voronoi diagram. The job of voronoi diagram split complete region into small cell based on minutiae points is there in images. All the points in the cell around mi or closure to mi than to any other minutiae. After that the Delaunay triangulation is formed by joining the centre of every pair of neighbouring in voronoi region. Next Delaunay pentangle can be formed by combining any three Delaunay triangles.

      Database

      Fingerprint

      image

      Pre

      processing

      Minutiae

      Extraction

      Delaunay Pentangle Matching

      Fingerprint

      image

      Pre

      processing

      Minutiae

      Extraction

      Delaunay Pentangle Matching

      Accept Or Reject

      Fig.6. Block diagram of Delaunay pentangle based fingerprint authentication system.

   4. Performance evaluation of different Delaunay based structures:

   To evaluate the performance of Delaunay based structure for fingerprint authentication, three performances are utilized: (1) false accept rate (FAR), which is defined as the ratio of successful impostor attempts to the total impostor attempts, (2) false reject rate (FRR), which is defined as the ratio of unsuccessful genuine attempts to total genuine attempts, (3) equal error rate (EER), which is defined as the error rate when FAR and FRR are equal.

   To evaluate the performance of Delaunay based structures, we set each image from each finger in database as the template image and compare it with seven images from the same fingers to calculate the FRR. And we set the 1st image from each finger in the database as the template to compare it with remaining fingers in the database to calculate the FAR. The genuine matching attempts is

   ( (8×7)/2)x10=280 and imposter matching attempts ((10×9)/2)= 45 are made for FVC2002 DB2.

   In order to evaluate the performance with three different structures are (1) Delaunay triangle based structure, (2) Delaunay quadrangle based structure and (3) Delaunay pentangle based structure, over the publicly available database FVC2002 DB2 detailed information is shows in Table 1.

   Table 1. Detailed information of FVC2002 DB2.

   Parameter	2002DB2
   Resolution	569 dpi
   Number of fingers	10
   Number of images per finger	8
   Sensor type	Optical sensor
   Image size	560×296
   Image quality	Medium

   Fig. 7 Performance evaluation of Delaunay based structure.

   The performance evaluation of these three different structures is illustrated in figure 7. It can be observed from figure 7 that the Delaunay pentangle based structure (EEE= 1.05%) exhibits best perform than Delaunay triangle (EER= 4.02%) and Delaunay quadrangle based structures (EER= 1.68%). This proves that the Delaunay pentangle structure is more stable than Delaunay triangle and Delaunay quadrangle based structures

   Method	2002DB2 EER (FRR/FAR)
   Delaunay Triangle based structure for fingerprint authentication	4.02%
   Delaunay quadrangle based structure for fingerprint authentication	1.68%
   Delaunay pentangle based structure for fingerprint authentication	1.05%

   Method	2002DB2 EER (FRR/FAR)
   Delaunay Triangle based structure for fingerprint authentication	4.02%
   Delaunay quadrangle based structure for fingerprint authentication	1.68%
   Delaunay pentangle based structure for fingerprint authentication	1.05%

   Table 2. Performance comparison of Delaunay based structures using FVC2002 DB2.

3. CONCLUSION

This paper presented the related works and performance analysis of Delaunay based structures for fingerprint authentication system. Performance analysis of Delaunay pentangle based structure achieves better performance than Delaunay triangle and Delaunay quadrangle based structures. It is survey that a Delaunay algorithm is the best recognition method fingerprint authentication. The performance of Delaunay pentangle based structure guaranteed low EER= 1.05% than other Delaunay based structure.

ACKNOWLEDGEMENT

I would like to thank my guide Dr. G. Mary Amirtha Sagayee, Professor, Department of Electronics and Communication Engineering, Parisutham Institute of Technology and Science, Thanjavur for her help and guidance to enable me to propose this system.

REFERENCES

[1] W.Yang, J. Hu, and s.wang, Delaunay quadrangle based fingerprint authentication system with template protection using topology code for local registration and security enhancement Inform. forensics and security, vol. 9, no. 7, pp.1556-6013, July 2014.

[2]R.Cappelli, D. Maio, and D. Maltoni, Modelling plastic distortion in fingerprint images, in Proc. ICAPR, 2001, pp. 369-379.

[3]F. Farooq, R. M. Bolle, T. Y. Jea, and N. Ratha, Anonymous and revocable fingerprint recognition, in Proc. IEEE CVPR Conf., Jun. 2007, pp. 17.

1. Y. Dodis, R. Ostrovsky, L. Reyzin, and A. Smith, Fuzzy extractors: How to generate strong keys from biometrics and other noisy data, SIAM J. Comput., vol. 38, no. 1, pp. 97139, Sep. 2008.

2. W. Yang, J. Hu, S. Wang, and J. Yang, Cancelable fingerprint templates with Delaunay triangle-based local structures, in Cyberspace Safety and Security. New York, NY, USA: Springer- Verlag, 2013, pp. 8191.

3. W. Yang, J. Hu, and S. Wang, A Delaunay triangle-based fuzzy extractor for fingerprint authentication, in Proc. 11th Int. Conf. Trust, Security Privacy Comput. Commun., 2012, pp. 6670.

[7]G. Parziale and A. Niel, A fingerprint matching using minutiae triangulation, in Proc. Biom. Authenticat., 2004, pp. 241248.

1. R.Soleymani and M.C. Amirani, A hybrid fingerprint matching algorithm using Delaunay triangulation and Voronoi diagram, in Proc.20th ICEE, 2012, pp. 752757.

2. A. A. Khanban and A. Edalat, Computing Delaunay triangulation with imprecise input data, in Proc. 15th Can. Conf. Comput. Geometry, 2003, pp. 9497.

[10]G. Bebis, T. Deaconu, and M. Georgiopoulos, Fingerprint identification using Delaunay triangulation, in Proc. Int. Conf. Inform. Intell. Syst., 1999, pp. 452459.

[11] M. Abellanas, F. Hurtado, and P. A. Ramos, Structural tolerance and Delaunay triangulation, Inform. Process. Lett., vol. 71, nos. 56, pp. 221227, Sep. 1999.