A Comparative Study on Fingerprint Matching Algorithms

A Comparative Study on Fingerprint Matching Algorithms

Rahul Gaikwad

Department of Computer Engineering Vidyavardhinis College of Engineering and Technology

(Mumbai University) Vasai,India

Sangita K. Chaudhari

Department ofCcomputer Engineering Vidyavardhinis College of Engineering and Technology

(Mumbai University) Vasai,India

Sairaj Jadhav

Department of Computer Engineering Vidyavardhinis College of Engineering and technology

(Mumbai University) Vasai,India

Abstract fingerprints are studied and analyzed from a long duration of time and it has been identified that it has a vital role to play in the upcoming and future applications. However matching two fingerprints is quiet a complex process and can go wrong due to different reasons or problems in the method used for matching. In this project we are going to compare the various fingerprint matching algorithms. We are going to compare three matching techniques are direct matching, minutiae matching and matching based on Ratios of distance. We are going to test various datasets and identify which is the best out of the three algorithms that we are going to study based on various parameters such as cost, time complexity and accuracy.

KeywordsFingerprint, algorithms, minutae, fingerprint matching, complexity, parameters (key words)

1. INTRODUCTION

   Biometrics have become a integral part of our life and used almost in each and every field today. From the biometrics, fingerprints are used in variety of applications both forensics and government applications. Also the fingerprint matching is the important and critical part in the study of fingerprints. The skin on our fingers consists of ridges and valleys. This ridges and valley pattern vary from person to person. This patterns are used to match the fingerprints. If the ridge-valley pattern of one finger matches the ridge- valley pattern of any other finger then the fingerprints are said to be matched, otherwise they are different from each other. The are various techniques and algorithms which have been evolved over the years for finding out the fingerprints are matched or not. But there is always a question to find out which is the best algorithms of the various evolved over the years. The parameters on which these algorithms are compared are cost, time complexity and accuracy to match the twofingerprints.

   We are going to perform a comparative analysis of a three random algorithms in this project. The algorithms will be explained in detail ahead in this paper.

2. MORE ABOUT FINGERPRINTS.

   1. Ridges and valleys

      Ridges and valleys are the important components of fingerprint matching study. Ridges and valleys are present at the tip of fingers. The extreme points and the crossing points of the ridges are called minutae. Also the point at which the ridge bifurgates into two ridges is called as the bifurgation.

      The minutae pattern of each fingerprint of a individual is different and does not change during his entire life. For matching of fingerprints a method called minutae based matching is widely accepted and we are going to compare the algorithms based on this method.

      Figure 1. Minutiae Ending and Bifurcation

   2. Verification and identification

   In verification, the input is fingerprint query along with an identity (ID). The system verifies that whether the ID is acted in a same way with the fingerprint or not. Whereas in identification, the input is the fingerprint query which is compared with the existing database and then its determined that it is matching or not.

   we are handling the verification problem. Although fingerprint recognition is research for over a period of time, and the progress done is also remarkable. The performance of

   even state-of-the-art matchers is much less than the expectations of theory estimation. Therefore, more efforts are needed to improve both the performance and the speed of fingerprint recognition systems.

   The matching algorithm plays a very important role in a fingerprint recognition system.

   B. Minutae based matching algorithm:

   In this algorithm, the minutae points of the query and and template fingerprints are taken and represented in the form of vectors, every element of this vector is a minutae point and which may describe by different properties such as position, type, orientation, quality of the neighbourhood region, etc. Let A and B be the feature vectors representing the minutae points, which form the template and query fingerprints respectively. Mostly this points are represented by using a triad of x, y and where is the minutae angle. Consider the number of minutae in A and B to be m and n respectively. And the equation is as follows:

   A = m1 , m2 ,…, mm ,

   B = m ' , m ' , …, m ' m ' = x ' , y ' ,

   1 2 ni j j j

   A = m1 , m2 ,…, mm ,

   B = m ' , m ' , …, m ' m ' = x ' , y ' ,

   1 2 ni j j j

   m

   m

   i xi , yi ,i , i 1…m

   , j 1…n

   j

   (1)

   A minutiae mi in A and mj in B are considered matching,

   if following conditions are satisfied:

   sd ( m ' j , mi )	x ' j xi 2 y	' j yi	2	ro (2)
   dd m ' j , mi min	' j i ,3	60 '	j i	o

3. ALGORITHMS

   In this paper we are going to compare three algorithms which we have discussed earlier. The three algorithms are discussed in detail below as follows:

   A. Direct matching algorithm:

   In this algorithm, the two fingerprint images are is the matched using their pixels. The input and template images are taken into considered for matching the two images.

   In the above equation, r0 and 0 are the parameters of tolerance which are required to reduce the amount of errors caused due to plasticity of skin. The count of matching points can be increased if the query image and the template image are aligned properly and correctly. Correctly alignment of two fingerprints can be done by searching a complex geometrical transformation function (map ()), that maps the two minutiae set (A and B) the desirable characteristics of map () functions are: it should be tolerant distortion; it should recover rotation, translation and scale parameters correctly.

   The above figure shows the flow diagram of the minutae based algorithm and there are two methods which are shown in the above design but the one which we are going to use for the implementation of our project or rather we can for the minuatae based matching is the binarized fingerprint method. This method includes following steps which are as follows:

   1. Thinning of image.

   2. Minutae detection.

   3. Minutae matching using euclidean distance.

   4. Displaying that images are matched or not with match percentage.

   C. Ratios of relational distance matching algorithm:

   In this algorithm, the main objective is to find out common minutae points set of the two fingerprint images. Out of the two fingerprint images with P1and P2 recognized minutiae points respectively (where P1 need not be equal to P2), this phase outputs the M common minutiae points, which would be present in both the images respectively. P1 represents the set of minutae points in the first image whereas P2 represents the set of minutae points in the second image and Mrepresents the intersection of P1 and P2 respectively. M- is a tuple that contains the information of the minutae and would recognize it uniquely among the all sets of minutae. The M- tuple of both images is compared and then it is determined whether the images are matched or not. In this algorithm, there is a base image and a input image, based on this the comparison is done. This algorithm contains least no of procedures and steps.

   M-(I) Tuples in base image (BM):

   For each minutiae i = 1 to P1, the 5 nearest minutiae points are found. This is done by calculating the Euclidean Distances from the ith minutiae point to all the other minutiae points in the set P1 (BM) and recording the 5 nearest minutiae points with respect to Euclidean Distances of them. If i1, i2, i3, i4 and i5 are the 5 nearest minutiae points of i, then we calculate M (i) tuple in the following way:

   1. Calculate distance:

      i i1, i i2, i i3, i i4, and i i5. Note that distance i iN means the Euclidean Distance between the points i and iN. So here, distance i i1 means the Euclidean distance between minutiae point i and i1 and so on.

   2. Find the following 10 ratios

   (i – i1): (i – i2), (i – i1): (i i3), (i – i1): (i i4), (i – i1): (i i5) ,

   (i i2) : (i i3), (i i2) : (i i4), (i i2) : (i i5), (i i3) :

   (i i4), (i i3) : (i i5), (i i4) : ( i i5).

   Based on this procedure the algorithm finds the match between two fingerprint images.

4. COMPRATIVE ANALYSIS

   In this comparative study of all the three algorithms it can be concluded that the direct matching requires very high end specification and cannot be implemented in simple or small scale computers, also the minutae based algorithm. In project we have performed the working of all the three algorithms together and we came to a conclusion that the minutae based matching method is the best in terms of time complexity, accuracy and also it uses the least memory among the three algorithms we have compared in this project. Verification and identification both can be done easily in this algorithm.

   So if this three algorithms were used in EVM for testing purpose so the result was again in the favor of minutae based algorithm.

   In the comparative study it has been proved that minutae based algorithm is the best among the three.

5. CONCLUSION

   In over the years, fingerprints have been used in variety of applications such as identifying a person or a authorized user to access any secret information, this study gives us that which algorithm in the current scenario can be considered for further research. This comparative study of algorithms will help to use any of this algorithms with a certain upgradation possible in electronic voting machine also.

   We have a conclusion that minutae based algorithm is the best so far out of three which we have compared. This could change at a certain level in future if there is some research or adavancement in this field and it can be assured that there will be because biometrics are unique and best source of authentication any time.

6. ACKNOWLEDGEMENT

   This work is a part of a Research Project and authors are thankful to UGC for funding the Project (File No. F-38- 258/2009 (SR) Dt: 19.12.2009).The authors would like to thank the anonymous reviewers for their thorough reviews, and constructive suggestions which significantly enhance the presentation of the paper.

7. REFERENCES

1. Pankanti S., Prabhakar S., Jain A.K., On the individuality of fingerprints, IEEE Trans. Patter Anal. Mach. Intell. 24 (8) pp: 1010- 1025, 2002.

2. Jain A.K., Hong L., Pankanti S., Bolle R., An identity-authentication system using fingerprints, Proc. IEEE 85 (9) pp: 1364-1388, 1997.

3. Jiang X., Yau W.Y., Fingerprint minutiae matching based on the local and global structures, Proceedings of the International Conference on Pattern Recognition, pp. 1038-1041, 2000.

4. Kovacs-Vajna Z.M., A fingerprint verification system based on triangular matching and dynamic time warping, IEEE Trans. Pattern Anal. Mach. Intel. 22 (11):1266-1276, 2000.

5. Saleh A.A., Adhami R.R., Curvature-based matching approach for automatic fingerprint identification, Proceedings of the Southeastern Symposium on System Theory, pp. 171-175, 2001.

6. Jain A.K., Prabhakar S., Hong L., Pankanti S., Filterbank-based fingerprint matching, IEEE Trans. Image Process. 9 (5): 846-859, 2000.

7. Jain A.K., Ross A., Prabhakar S., Fingerprint matching using minutiae and texture features, Proceedings of the International Conference on Image Processing, vol. 3, pp. 282-285, 2001.

8. Ceguerra A.V., Koprinska I., Integrating local and global features in automatic fingerprint verification, Proceedings of the International Conference on Pattern Recognition, vol. 3, pp. 347-350, 2002.

9. Xuejun Tan, Bir Bhanu, Fingerprint matching by genetic, algorithms, Pattern Recognition Society. Published by Elsevier Ltd, 39 pp: 465- 477, 2006.

10. Robert S. Germain, Andrea Califano, And Scott Colville,

    Fingerprint Matching Using Transformation Parameter Clustering, theme article, IEEE Computational Science & Engineering, 1997.

11. Gold S. and Rangarajan A., A graduated assignment algorithm for graph matching, IEEE Transactions on Pattern Analysis and Machine Intelligence., vol. 18, no.4, pp.377-388, 1996.

12. Hrechak A.K. and Mchugh J.A., Automated Fingerprint Recognition using Structural Matching, Pattern Recognition, vol. 23, pp. 893-904, 1990.

13. Eshera M. and Fu K.S., A Similarity Measure between Attributed Relational Graphs for Image Analysis, in Proceedings of the 7th International Conference on PatternRecognition, Montreal, P.Q., Canada, July 30-Aug 3 1984.

14. Ratha N.K, Pundit V.D, Bolle R.M, Vaish V., Robust Fingerprint Authentication Using Local Structural Similarity, Workshop on Applications of Computer Vision, pp: 29-34, 2000.

15. Ranade A. and Rosenfeld A., Point Pattern Matching byRelaxation,Pattern Recog., vol, no: 12, 2; pp: 269-275, 1993.

16. Ton J. and Jain A.K., Registering landsat images bypoint matching,IEEE Transactions on GeoSci. RemoteSensing, vol.27, pp. 642-651, May 1989.

17. Jain A.K., Hong L., Pankanti S. and Bolle R., An identity authentication system using fingerprints, Proc. IEEE,vol.85, pp.

    1365-1388, Sept.1997.

18. Ölz W. and Kropatsch W.G., Graph Representation of Fingerprint Topology, Computer Vision – CVWW'04, Slovenien Pattern Recognition Society, pp. 51-58, 2004.

19. Chikkerur S., Cartwright A. N. and Govindaraju V., "Kplet and CBFS: A Graph based Fingerprint Representation and Matching Algorithm," ICB 2006.

20. Sanjay Kumar, Ekta Waliam., Analysis of Electronic Voting System in Various Countries, International Journal on Computer Science and Engineering (IJCSE), ISSN: 0975-3397 Vol. 3 No. 5 May 2011.

21. Meltemp Ballan, Ayhan Sakarya F. and Brian L. Evans, "A Fingerprint Classification Technique Using Directional Images", 1997..

22. Mercuri R.. Electronic Vote Tabulation Checks and balances, PhD thesis, University of Pennsylvania, Philadelphia, PA, Oct.2000.

23. Ridges and Furrows-history and science of fingerprint identification technology and legal issues. http://ridgeand.furrows.homestead.com/fingerprint.html

24. Voting: What Is; What Could Be, MIT Voting Technology Project, July 2001

25. https://support.smartbear.com/testcomplete/docs/testing- with/checkpoints/regions/how-image-comparison-works.html

26. https://www.researchgate.net/figure/Block-diagram-of-the-proposed-

    Algorithm_fig4_44797156

27. https://www.researchgate.net/figure/Block-diagrams-of-enrollment- verification-and-identification-tasks-are-shown-using- the_fig1_278667358

li>

Abinandhan Chandrasekaran, Dr.Bhavani Thuraisingham,

Fingerprint Matching Algorithm Based on Tree Comparison using Ratios of Relational Distances Second International Conference on Availability, Reliability and Security (ARES'07), IEEE Computer society 2007.