DESIGNING A NOVEL APPROACH FOR FINGERPRINT BIOMETRIC DETECTION: BASED ON MINUTIAE EXTRACTION

International Journal on Bioinformatics & Biosciences (IJBB) Vol.2, No.4, December 2012 11 DOI : 10.5121/ijbb.2012.2402 D ESIGNING A N OVEL A PPROACH FOR F INGERPRINT B IOMETRIC D ETECTION : B ASED ON M INUTIAE E XTRACTION Hossein Jadidoleslamy Information Technology Engineering Group, Department of Information Technology, Communications and Security, University of Malek Ashtar, Tehran, Iran [email protected] A BSTRACT People authentication based on fingerprint is one of the most important people authentication techniques which it used biology specifications. The main purpose of this paper is discussing on minutiae-based extraction methods for fingerprints comparison and presenting a new pattern matching algorithm in this area; of course, this algorithm also has been presented based on comparing fingerprint features (especially minutiae points). K EYWORDS Biometric, Fingerprint, Minutiae, Automated Fingerprint Identification System (AFIS), Extraction, Matching 1. I NTRODUCTION Fingerprint is unique for any people and it can be used as peoples' signature to authenticate them [1, 2]. The most famous softwares of this category is using on criminology. Nowadays, it is increasing request for automatic comparison of fingerprints. Some of this system's applications are as following: • Access control to the physical places; • Access control to the computer, network and other resources; • Access control to the customers' banking accounts; In other side, while comparing fingerprint images, it is possible to occur following errors: • Different scratch; • Destroyed and incomplete fingerprint; • Inappropriate image (inappropriate deployment location of finger on the scanner glass or being displaced the finger rather than special situation or being rotated the finger with special angle lead to incomplete and italic image of finger on scan process); An advanced solution for solving this problem is extracting the features of fingerprint image (such as start, end and intersection points of fingerprint lines) and then, doing comparison between different sets of fingerprint features. However, the presented solution requires to an advanced and reliable algorithm to process fingerprint image; this algorithm should be had following capabilities: • Removing scratch [3, 24]; • Features extraction [8, 9, 12, 19]; • Displaced or rotated fingerprint comparison [24, 25]; • Being fast to be applicable in environments, along with many users; International Journal on Bioinformatics & Biosciences (IJBB) Vol.2, No.4, December 2012 12 • The volume and size of extracted features (for storing into the information-base on microchip); Although there are many algorithms to verify fingerprint [4, 5], it is not easy to acquiring a comprehensive solution to obviating all requirements. This paper has been organized into 7 sections, including: section2 will discuss about fingerprint based systems; section3 represented some discussions about fingerprint and its various properties; section4 posed pattern extraction methods; section5 presented the proposed pattern matching algorithm and different kinds of fingerprint scanners; section6 expressed the conclusion; and finally, section7 presented some posed and new research topics on this domain. 2. F INGERPRINT -B ASED S YSTEMS The most important challenge of governments in current century is counter-measuring with biggest century spoofing; i.e. identity forgery or impersonation and it is only possible by using of biometric parameters. At the current time, biometric plays an important role on following areas: • Peoples' verification; • Access control; • Computer security; • Banking; • Access times; • Unknown peoples' specification; As Figure1 shows, fingerprint biometric systems have functionalities such as image receipt, image process, features extraction [19] and pattern matching [20, 21]. These softwares are calling AFIS (Automated Fingerprint Identification System) [3, 4]. The necessity of producing an AFIS software is technical and scientific fingerprint verification [3, 5, 6]. In next sections, the paper will be discussed about fingerprint verification based on pattern, features verification, features extraction and how to comparing fingerprints. Following figure is showing how an AFIS system operates [3, 13]. Figure 1. Functionality of an AFIS 3. F INGERPRINT D IFFERENT D IMENSIONS 3.1. Fingerprint Feature Extraction International Journal on Bioinformatics & Biosciences (IJBB) Vol.2, No.4, December 2012 13 Fingerprint feature extraction is the most important process in AFIS systems [3, 10]. By attention to the used algorithm capability, this process is verifying different features of a fingerprint (such as minutiae points, core, delta and pattern) and it is storing them into a data structure (called template). This data structure can be according to the NIST specified standards or a special structure of used algorithm [11]. But a good algorithm has capability to converting its template to the NIST standards and vice-versa. Also, it is possible to discussing about presenting new templates for storing the template; it is necessity to attention to the following hints for creating this template, such as: • Being small the size and volume of the template; since, it leads to increasing of comparison speed and it provides possibility of storing templates in smart cards, too; • Removing unnecessary features of the template; so that it requires to less memory and leads to comparison speed increment; As a result, more features leads to increasing the comparison accuracy and then, more precise result and also, it leads to volume and size increment and comparison speed reduction; therefore, by attention to the case of algorithm applicability should select best option (it is necessary to have be existed balance and fairness between templates volume, size, search speed, comparison accuracy and speed). For example, in criminal authentication systems, accuracy of verification [6, 7] has more important rather than volume, size and speed parameters. 3.2. Fingerprint Template The first difference between fingerprints is created design and template of fingerprint lines (it called "pattern" and it be categorized as "classification"). Following figure (Figure2) is showing three different patterns. These patterns are dividing into 4 major categories, including: • Whorl; • Left Loop (LL); • Right Loop (RL); • Arch; Figure 2. Different Types of Fingerprint Patterns 3.2.1. Whorl Pattern In the Whorl pattern, fingerprint lines create concentricity circles image. International Journal on Bioinformatics & Biosciences (IJBB) Vol.2, No.4, December 2012 14 3.2.2. Left Loop Pattern In the Left Loop pattern, it is possible to see a rotation or curvature on the left direction of image. 3.2.3. Right Loop Pattern The Right Loop pattern has the similar rotation or curvature on the right direction of image. 3.2.4. Arch Pattern In the Arch pattern, there are some arches in the form of Hill in the middle of image. It is clear completely which it is not required to comparing 2 different patterns' fingerprints while comparing fingerprints; since the probability of matching 2 fingerprints with various and different patterns is zero. Of course, the most automated systems do not use the matching of these features for comparison [22, 23]. Because it is possible to acquiring a correct pattern of fingerprint from a vertical and complete input image (no rotation); but usually the incoming image do not has these features (it may be had rotation, curvature or it may be incomplete); so it will not be had the required features; this leads to increase the probability of incorrect detection or recognition [17, 18]; then, it leads to error or fault. The main application of this feature on the identity verification systems is classifying fingerprint cards [4, 7]. 3.3. Fingerprint Features Fingerprint features are points which they are observable and distinguishable from collision fingerprint lines or curve forms. These points create the base of fingerprint verification process. In Figure3, there are three different kinds of fingerprint features [24, 25]. Figure 3. Different Features of a Fingerprint Pattern These features have been divided into 4 major classifications, including: Minutiae, Core, Double Core and Delta. Minutiaes are start, end, collision and 2-branched points of fingerprint lines which they create the base of fingerprints comparison and they have been specified by green color in above figures. The core is the center of rotation in RL (Right Loop) and LL (Left Loop) patterns which they have been determined by red umbrella in the above figures. Double core is the center of circle in Whorl pattern. International Journal on Bioinformatics & Biosciences (IJBB) Vol.2, No.4, December 2012 15 Deltas are rectangle form points which they have been created from lines collision and they usually be seen in the right or left direction of loops, which they have been shown by red color tripetalous sign in above figures. All of these features are stored into a date structure which it is created by fingerprint algorithm programmers (it called "template") and while comparing fingerprints, the templates be compared to each other. There are some standards to storing fingerprint features which they have been created by NIST [11]. Size and volume of template is an important factor which it is affected on speed of comparison and microchips' storage capacity. Any one of these features should be had a special data structure. For example, following data structures are proposed for fingerprints' features and their templates. 3.3.1. Date Structure to Storing Minutiae Points typedef enum MinutiaType_ typedef struct Minutia_ { { mtUnknown = 0, short X; mtEnd = 1, short Y; mtBifurcation = 2, MinutiaType Type; mtOther = 3 byte Angle; } MinutiaType; byte Quality; byte Curvature; byte G; vector < MinutiaNeighbor > MinutiaNeighborSet; } Minutia; X, Y: A minutia coordinates in fingerprint image; Minutiae type: It determines type of minutiae (2-branched, line-end, island or etc); Angle: Minutiae angle into the image; Quality: Minutiae quality (it depends to the image quality); Curvature: Nearest slot to the minutiae (rather than fingerprint lines); G: Minutiae value or weight (amount of neighbor's minutiae, its type, situation and quality); Minutiae neighbor set: The set of points of neighbor's minutiae; 3.3.2. Data Structure to Storing Minutiae Points of Neighbors typedef struct MinutiaNeighbor_ { int Index; byte RidgeCount; } MinutiaNeighbor; Index: The number of neighbor's minutiae; Ridge count: The distance between neighbor minutiae and the candidate minutiae; 3.3.3. Data Structure to Storing Core Points typedef struct Core_ { short X; short Y; byte Angle; International Journal on Bioinformatics & Biosciences (IJBB) Vol.2, No.4, December 2012 16 } Core; X, Y: Core coordinates in the fingerprint image; Angle: The core angle into the image; 3.3.4. Data Structure to Storing Delta Points typedef struct Delta_ { short X; short Y; byte Angle1; byte Angle2; byte Angle3; } Delta; X, Y: Delta coordinates into the fingerprint image; Angle (X): Triple-angles of delta into the fingerprint image; 3.3.5. Data Structure to Storing Double Core Points typedef struct DoubleCore_ { short X; short Y; } DoubleCore; X, Y: The double core coordinates into the fingerprint image; 3.3.6. Data Structure to Storing Template typedef struct FingerprintRecord_ { short Index; short Class; vector <Minutia> MinutiaSet; vector <Core> CoreSet; vector <Delta> DeltaSet; vector <DoubleCore> DoubleCoreSet; } FingerprintRecord; Index: The fingerprint index; Class: The fingerprint pattern; MinutiaeSet: Set of minutiae points; CoreSet: Set of core points; DeltaSet: Set of delta points; DoubleCoreSet: Set of double core points; 4. M INUTIAE E XTRACTION T ECHNIQUES This process is including of direct detection of minutiae, binary image creation and image optimization steps; at the next sections, these steps have presented in comprehensive. 4.1. Minutiae Direct Detection Automatic detection of minutiae is very important processes, especially in fingerprint along with low quality; while that signal disorder and contrast shortage leads to forming pixel similar to a International Journal on Bioinformatics & Biosciences (IJBB) Vol.2, No.4, December 2012 17 minutiae or being hide real minutiae. In this method, a new technique has been proposed based on following lines lump; it extracts minutiae from the gray-scale image, directly [9, 10, 15]. According to the Figure4, this method at the first step finds and specifies the fingerprint lines path by using of an especial algorithm; for this purpose, a gray-scale image be used; into this image, the fingerprint lines prominence being shown by a spectrum of gray pixels which the most prominence will be shown by most severity of dark color (the most prominence will show the line path). The fingerprint lines will be specified by finding these maximums and tracking them. As Figure4 is showing, a pseudo-code of above algorithm can be as follows. Figure 4. The First Step of Minutiae Direct Detection Algorithm and Its Pseudo-code According to the Figure5, in the second step, minutiae points should extract from the acquired lines; it is possible to have be existed a minutiae whereas lines has been ended or they cut off each other. So, for this purpose, all of acquired lines of the image should be scanned in once; it is possible to use of an algorithm which it creates a second image (including of detected lines) from the primary image and it signs lines by scanning or traversing them; when all lines be signed, i.e. the whole image has been scanned. As Figure5 shows, a pseudo-code for minutiae detection algorithm can be as follows. International Journal on Bioinformatics & Biosciences (IJBB) Vol.2, No.4, December 2012 18 Figure 5. The Second Step of Minutiae Direct Detection Algorithm and Its Pseudo-code 4.2. Binary Image Creation Figure6 is showing how can create a binary image; this method is a common algorithm in AFIS systems which it converts the fingerprint primary image to the gray-scale format and then, by using of an especial process, it will be converted to a binary image [3, 17, 26]. The goal of this conversion is being specified fingerprint lines in attention to the color severity difference in prominence or hill points of lines and slots. When being determined these lines, it is possible to find minutiae points of lines, intersection points and start or end of lines. International Journal on Bioinformatics & Biosciences (IJBB) Vol.2, No.4, December 2012 19 Figure 6. Gray-scale Image to Binary Image Conversion In different algorithms, the main difference is in primary image process [26]; after primary process, extracting minutiae points is almost same and it uses of similar techniques. By attention to the Figure7, the minutiae are classified into 2 main types, including: 1. Bifurcation: in this case, minutiae are determined from intersection location of 2 lines (connection or intersection point); 2. End: in this case, minutiae are the end points or start points of lines; Figure 7. Different Types of Minutiae Point Extraction 4.3. Image Optimization This method can be used as a pre-process for all minutiae-extraction algorithms [8, 9, 14, 26]. In this method the primary image of fingerprint be processed and a part of image be filtered which it is ambiguous or it has not appropriate quality and it increases the probability of detecting false minutiae (be filtered). Also, an image part which it can be reconstructed, it be improved navigation. For example, some of fingerprint lines which they are clear, but in part of image has been removed from the created image; due to scratch or incomplete contact of finger with scanner [25], they have to be reconstructed. After doing this process, the minutiae extraction will be did from an appropriate, more reliable and better quality image which it will be significant on result of comparison and fingerprints' verification [15, 16, 26], directly. 5. T HE P ROPOSED P ATTERN M ATCHING A LGORITHM 5.1. Fingerprints' Comparison Fingerprints' comparison is started by comparing templates, that it is based on finding similarity between minutiae points of 2 fingerprints' templates. Neighbor minutiae are told to points which they are placed near to the candidate minutiae and they are selected by 2 methods, including: 1. Selection with angle P/2; 2. Selection with angle P/4; International Journal on Bioinformatics & Biosciences (IJBB) Vol.2, No.4, December 2012 26 R EFERENCES 1. M. K. Khan, “Fingerprint Biometric-based Self Authentication and Deniable Authentication Schemes for the Electronic World”, IETE Technical Review, Volume 26, Issue 3, 2009. 2. A. K. Jain, L. Hong, S. Pankanti, and R. Bolle, “ An identity authentication system using fingerprints”. Proc. IEEE, 85(9), 1997, pp.1365–1388. 3. P. Komarinski, “Automated Fingerprint Identification System (AFIS)”, Elsevier Academic, USA, 2005. 4. M. Kaur, M. Singh, P.S. Sandhu, “Fingerprint Verification system using Minutiae Verification Technique”, Proceedings of world Academy of Science, Engineering and Technology, Vol. 36, 2008. 5. R. Cappelli, D. Maio, J. L. Wayman, and A. K. Jain, “Performance evaluation of fingerprint verification systems”, IEEE Transactions on Pattern Analysis and Machine Intelligence”, 28(1), 2006, pp. 3–18. 6. S. Chikkerur, V. Govindaraju, S. Pankanti, R. Bolle, and N. Ratha, “Novel approaches for minutiae verification in fingerprint images”, in Seventh IEEE Workshops on Application of Computer Vision (WACV/MOTION’05), Vol. 1, 2005, pp. 111–116. 7. S. Prabhakar, J. Wang, A. K. Jain, S. Pankanti, and R. Bolle, “Minutiae Verification and classification for fingerprint matching”. Proc. 15th International Conference Pattern Recognition (ICPR) Vol. 1, 2000, pp. 25–29. 8. C. Ryu, S. G. Kong and H. Kim, “Enhancement of feature extraction for low-quality fingerprint images using stochastic resonance”, Pattern Recognition Letters, Vol. 32, 2011, pp. 107-113. 9. R. Kaur, P. S. Sandhu and A. Kamra, “A Novel Method for Fingerprint Feature Extraction”, In Proc. International Conference on Networking and Information Technology, 2010. 10. P. Gnanasivam and S. Muttan, “An efficient algorithm for fingerprint preprocessing and feature extraction”, ICEBT 2010, Procedia computer Science, Vol. 2, 2010, pp.133-142. 11. S. Maddala, S. R. Tangellapally, J. S. Bartunek and M. Nilsson, "Implementation and evaluation of NIST Biometric Image Software for fingerprint recognition," Biosignals and Biorobotics Conference (BRC), 2011 ISSNIP, pp.1-5. 12. X. Gao, X. Chen, J. Cao, Z. Deng, C. Liu and J. feng, “A Novel Method Of Fingerprint Minutiae Extraction Based On Gabor Phase”, In Proc. IEEE International Conference on Image Processing, 2010, pp. 3077-3080. 13. B. N. Lavanya, K. B. Raja, K. R. Venugopal, L. M. Patnaik, "Minutiae Extraction in Fingerprint Using Gabor Filter Enhancement," In Proc. International Conference on Advances in Computing, Control, & Telecommunication Technologies, 2009, pp.54-56. 14. Zhao Feng, Xiaou Tang, “Preprocessing and post processing for skeleton-based fingerprint minutiae extraction”, Pattern Recognition, Vol. 40, 2007, pp. 1270-1281. 15. M. Gamassi, V. Pivri and F. Scotti, “Fingerprint local analysis for high performance minutiae extraction”, IEEE International Conference on Image Processing (ICIP), Vol. 3, 2005, pp. 265268. 16. K. K. Hartwig Fronthaler and J. Bigun, “Local feature extraction in fingerprints by complex filtering”, In Advances in Biometric Person Authentication, LNCS, Vol. 3781, 2005, pp.77–84. 17. S. Zorita, O. Garcia, C. Llanas and G. Rodriguez; “Minutiae extraction scheme for fingerprint recognition systems”, In Proceedings of the International Conference on Image Processing; Vol. 3, October 2001, pp. 254–257. 18. L. H. Thai and N. H. Tam, “Fingerprint recognition using standardized fingerprint model”, IJSCI International Journal of Computer Science Issues, Vol. 7, Issue 3, No. 7, 2010, pp. 11-16. 19. B. Bir and T. Xuejun, “Fingerprint indexing based on novel features of minutiae triplets”, IEEE Transactions on IJCSI International Journal of Computer Science Issues, Vol. 8, Issue 5, No. 3, September 2011; 20. A.R. Patil, M. A. Zaveri, "A Novel Approach for Fingerprint Matching Using Minutiae", In Proc. Fourth Asia International Conference on Mathematical/Analytical Modelling and Computer Simulation (AMS), 2010, pp.317-322. 21. F. Chen, J. Zhou and C. Yang, “Reconstructing Orientation Field from Fingerprint Minutiae to Improve Minutiae Matching Accuracy”, IEEE Transactions on Image Processing, Vol. 18, No. 7, 2009, pp. 1665-1670. International Journal on Bioinformatics & Biosciences (IJBB) Vol.2, No.4, December 2012 27 22. K. Cao, X. Yang, X. Tao, P. Li, Y. Zang and J. Tian, “Combining features for distorted fingerprint matching”, Journal of Network and Computer Applications, Vol. 33, 2010, pp. 258267. 23. H. Choi, K. Choi and J. Kim, “Fingerprint Matching Incorporating Ridge Features With Minutiae”, IEEE Transactions on Information Forensics and Security, Vol. 6, No. 2, 2011, pp. 338-345. 24. A. J. Willis and L. Myers, “A cost-effective fingerprint recognition system for use with lowquality prints and damaged fingertips”, Pattern Recognition, Vol. 34(2):255–270, 2001. 25. A.M. Bazen and S.H. Gerez, “Achievement and challenges in fingerprint recognition”, in Biometric Solutions for Authentication i an e-World, 2002, pp.23–57. 26. M. Usman Akram , A. Tariq, Shoaib A. Khan, “ Fingerprint image : pre and post processing”, Int. Journal of Biometrics, Vol. 1, No.1, 2008. Author Biography H. Jadidoleslamy is a PhD student in Information Technology (IT)-Information Security at the University of Malek Ashtar in Tehran, Iran. He received his Bachelor Degree in Information Technology (IT) engineering from the University of Sistan and Balouchestan (USB), Zahedan, Iran, in September 2009. He also has been received his Master of Science degree from the University of Guilan, Rasht, Iran, in March 2011. His research interests is including Computer Networks (especially Wireless Sensor Network), Information Security (by focusing on Intrusion Detection System), and E-Commerce. He may be reached at [email protected] or jadidoleslam[email protected]om.