A Survey on Fingerprint Mathing Algorithms

A Survey on Fingerprint Mathing Algorithms In this networked world, users store their significant and less significant data over internet (cloud). Once data is ported to public Internet, security issues pop-up. To address the security issues, the present day technologies include traditional user-id and password mechanism and a onetime password (two-factor authentication). In addition to that, using the inexpensive scanners built into smartphones, fingerprint authentication is incorporated for improved security for data communication between the cloud user and the cloud provider. The age old image processing technique is revisited for processing the fingerprint of the user and matching against the stored images with the central cloud server during the initial registration process. In this paper, various fingerprint matching algorithms are studied and analyzed. Two important areas are addressed in fingerprint matching process: fingerprint verification fingerprint identification. The former compares two fingerprint and says they are similar or not; while the latter searches a database to identify the fingerprint image which is fed in by the user. Based on the survey on different matching algorithms, a novel method is proposed. Keywords: image processing, biometrics, fingerprint matching, cloud, security Introduction Automated fingerprint recognition systems have been deployed in a wide variety of application domains ranging from forensics to mobile phones. Designing algorithms for extracting salient features from fingerprints and matching them is still a challenging and important pattern recognition problem. This is due to the large intra-class variability and large inter-class similarity in fingerprint patterns. The factors responsible for intra-class variations are a) displacement or rotation between different acquisitions; b) partial overlap, especially in sensors of small area; c) non linear distortion, due to skin plasticity and differences in pressure against the sensor; d) pressure and skin condition, due to permanent or temporary factors (cuts, dirt, humidity, etc.); e) noise in the sensor (for example, residues from previous acquisitions); f) feature extraction errors. Fingerprint identification system may be either a verification system or an identification system depending on the context of the application. A verification system authenticates a person’s identity by comparing the captured fingerprint with her/his previously enrolled fingerprint reference template. An identification system recognizes an individual by searching the entire enrolment template database for a match. The fingerprint feature extraction and matching algorithms are usually quite similar for both fingerprint verification and identification problems. Fingerprint – Identification and Verification using Minutiae Based Matching Algorithms Fingerprints are commonly used to identify an individual. Research also suggests that fingerprints may provide information about future diseases an individual may be at risk for developing. Fingerprints are graphical flow-like ridges in palm of a human. Fingerprint is captured digitally using a fingerprint scanner. Fingerprints are commonly used to identify an individual. Research also suggests that fingerprints may provide information about future diseases an individual may be at risk for developing. Fingerprints are graphical flow-like ridges in palm of a human, that are unique amongst human beings. The hardware, fingerprint scanners are becoming low cost devices. The two most important ridge characteristics are ridge ending and ridge bifurcation. Automatic fingerprint identification systems (AFIS) have been widely used. An AFIS consists of two phases: offline and online. In the off-line phase, a fingerprint is acquired, enhanced using different algorithms, where features of the fingerprint are extracted and stored in a database as a template. In the on-line phase, a fingerprint is acquired, enhanced and features of the fingerprint are extracted, fed to a matching model and matched against template models in the database as depicted in the figure 1. Among all the biometric techniques, fingerprint-based identification is the most common used method which has been successfully used in numerous applications. Comparing to other biometric techniques, the advantages of fingerprint-based identification are as detailed below: The minutiae details of individual ridges and furrows are permanent and unchanging. The fingerprint is easily captured using low cost fingerprint scanner. Fingerprint is unique for every person. So it can be used to form multiple passwords to improve the security of the systems. Flow of Diagram representing the Fingerprint Identification The above figure clearly explains the simple methodology of fingerprint verification. In off-line process, the fingerprint of all users are captured and stored in a database. Before storing the raw or original image, the image is enhanced. The fingerprint image when captured for the first time may contain unwanted data ie noise. Because our hands being the most used part of our body may contain wetness, dry, oily or grease; and these images may be treated as noise while capturing the original fingerprint. And hence, to remove the noise, image enhancement techniques like adaptive filtering and adaptive thresholding. Original Fingerprint Image. The standard form factor for the image size is 0.5 to 1.25 inches square and 500 dots per inch. In the above original image, the process of adaptive filtering and thresholding are carried out. The redundancy of parallel ridges is a useful characteristic in image enhancement process. Though there may be discontinuities in a particular ridge, we can determine the flow by applying adaptive, matched filter. This filter is applied to every pixel in the image and the incorrect ridges are removed by applying matched filter. Thereby, the noise is removed and the enhanced image is shown in figure 3. Enhanced Fingerprint Image The enhanced image undergoes feature extraction process wherein: binarization and thinning take place. All fingerprint images do not share same contrast properties as the force applied while pressing may vary for each instance. Hence, the contrast variation is removed by this binarization process using local adaptive thresholding. Thinning is a feature extraction process where the width of the ridges is reduced down to a single pixel. The resultant feature extraction is shown below figure 4. Feature Extraction After Binarization and Thinning The process of minutiae extraction is done as the last step in feature extraction and then the final image is stored in database. Operating upon the thinned image, the minutiae are straightforward to detect and the endings are found at the termination points of thin lines. Bifurcations are found at the junctions of three lines. Feature attributes are determined for each valid minutia found. These consist of: ridge ending, the (x,y) location, and the direction of the ending bifurcation. Although minutia type is usually determined and stored, many fingerprint matching systems do not use this information because discrimination of one from the other is often difficult. The result of the feature extraction stage is what is called a minutia template, as shown in figure 5. This is a list of minutiae with accompanying attribute values. An approximate range on the number of minutiae found at this stage is from 10 to 100. If each minutia is stored with type (1 bit), location (9 bits each for x and y), and direction (8 bits), then each will require 27 bits say 4 bytes and the template will require up to 400 bytes. It is not uncommon to see template lengths of 1024 bytes. Minutiae Template Now, the online process starts. At the verification stage, the template from the claimant fingerprint is compared against that of the enrollee fingerprint. This is done usually by comparing neighborhoods of nearby minutiae for similarity. A single neighborhood may consist of three or more nearby minutiae. Each of these is located at a certain distance and relative orientation from each other. Furthermore, each minutia has its own attributes of type (if it is used) and minutia direction, which are also compared. If comparison indicates only small differences between the neighborhood in the enrollee fingerprint and that in the claimant fingerprint, then these neighborhoods are said to match. This is done exhaustively for all combinations of neighborhoods and if enough similarities are found, then the fingerprints are said to match. Template matching can be visualized as graph matching that is comparing the shapes of graphs joining fingerprint minutiae. A 1:1 matching cannot be carried out and we use a threshold value – termed as match score, usually a number ranging between 0 and 1. Higher the value, higher is the match. Figure 6: Few- Matching in online process Minutiae are extracted from the two fingerprints and stored as sets of points in the two dimensional plane. Minutia-based matching consists of finding the alignment between the template and the input minutiae feature sets, that results in the maximum number of minutiae pairs. 1) Weiguo Sheng et.al In their paper, the authors proposed a memetic fingerprint matching algorithm that aimed to identify optimal global matching between two sets of minutiae. The minutiae local feature representation called the minutiae descriptor that had information about the orientation field sampled in a circular pattern around the minutiae was used by them in the first stage. In the second stage, a genetic algorithm(GA) with a local improvement operator was used to effectively design an efficient algorithm for the minutiae point pattern matching problem. The local improvement operator utilized the nearest neighbor relationship to assign a binary correspondence at each step. Matching function based on the product rule was used for fitness computation. Experimental results over four fingerprint databases confirmed that the memetic fingerprint matching algorithm(MFMA) was reliable. 2) Kai Cao et al A penalized quadratic model to deal with the non-linear distortion in fingerprint matching was presented by the above authors. A fingerprint was represented using minutiae and points sampled at a constant interval on each valid ridge. Similarity between minutiae was estimated by the minutia orientation descriptor based on its neighboring ridge sampling points. Greedy matching algorithm was adopted to establish initial correspondences between minutiae pairs. The proposed algorithm used these correspondences to select landmarks or points to calculate the quadratic model parameters. The input fingerprint is warped according to the quadratic model, and compared with the template to obtain the final similarity score. The algorithm was evaluated on a fingerprint database consisting of 800 fingerprint images. 3) Peng Shi et.al In their paper, the authors proposed a novel fingerprint matching algorithm based on minutiae sets combined with the global statistical features. The two global statistical features of fingerprint image used in their algorithm were mean ridge width and the normalized quality estimation of the whole image. The fingerprint image was enhanced based on the orientation field map. The mean ridge width and the quality estimation of the whole image were got during the enhancement process. Minutiae were extracted on the thinned ridge map to form the minutiae set of the input fingerprint. The algorithm used to estimate the mean ridge width of fingerprint, was based on the block-level on non-overlap windows in fingerprint image. Four databases were used to compute the matching performance of the algorithm. 4) Sharat Chikkerur et.al The local neighborhood of each minutiae was defined by a representation called K-plet that is invariant under translation and rotation. The local structural relationship of the K-plet was encoded in the form of a graph wherein each minutiae was represented by a vertex and each neighboring minutiae by a directed graph. Dynamic programming algorithm was used to match the local neighborhood. A Coupled Breadth First Search algorithm was proposed to consolidate all the local matches between the two fingerprints. The performance of the matching algorithm was evaluated on a database consisting of 800 images. 5) Jin Qi and Yang Sheng Wang They proposed a minutiae-based fingerprint matching method. They defined a novel minutiae feature vector that integrated the minutiae details of the fingerprint with the orientation field information that was invariant to rotation and translation. It captured information on ridge-flow pattern. A triangular match method that was robust to non-linear deformation was used. The orientation field and minutiae were combined to determine the matching score. They evaluated the performance of their algorithm on a public domain collection of 800 fingerprint images. 6) Atanu Chatterjee et.al Another method for fingerprint identification and verification by minutiae feature extraction was proposed by the above authors. Minutiae were extracted from the thinned ridges from the fingerprint images and these feature matrices were applied as input data set to the Artificial Neural Network. Post processing was done to remove false minutia. Back propagation algorithm was used to train the network. Extracted features of the input fingerprint were verified with stored trained weights and threshold values. Experiments were conducted on 160 fingerprint images and the proposed system exhibited an accuracy of 95%. 7) Tsai Yang Jea et.al A flow network-based fingerprint matching technique for partial fingerprints was introduced by. For each minutiae along with its two nearest neighbors, a feature vector was generated which was used for the matching process. Minimum cost flow (MCF) problem algorithm was used to find the one-to-one correspondence between the feature vectors and the list of possibly matched features was obtained. A two hidden layer fully connected Neural Network was proposed to calculate the similarity score. Their experiments on two fingerprint databases showed that using neural networks for generating similarity scores improved accuracy. 8) Marius Tico et.al They have proposed a method of fingerprint matching based on a novel representation for the minutiae. The proposed minutiae representation incorporated ridge orientation information in a circular region, describing the appearance of the fingerprint pattern around the minutiae. Average Fingerprint Ridge period was evaluated to select the sampling points around the minutiae. Matching algorithm was based on point pattern matching. To recover the geometric transformation between the two fingerprint impressions, a registration stage was included. The Greedy algorithm was used to construct a set of corresponding minutiae. Experiments were conducted on two public domain collections of fingerprint images and were found to achieve good performance. 9) Asker M.Bazen et. al A minutiae matching method using a local and global matching stage was presented by Asker M. Bazen et. Al. Their elastic matching algorithm estimated the non-linear transformation model in two stages. The local matching algorithm compared each minutia neighborhood in the test fingerprint to each minutia neighborhood in the template fingerprints. Least square algorithm was used to align the two structures to obtain a list of corresponding minutia pairs. Global transformation was done to optimally register the two fingerprints that represented the elastic deformations by a thin-plate spline (TPS) model. The TPS model describes the transformed coordinates independently as a function of the original coordinates. Local and global alignments were used to determine the matching score. Conclusion This paper, we presented Fingerprint identification and verification based on minutiae based matching. The original fingerprint captures is pre-processed and the pattern is stored in the database for verification and identification. The pre-processing of the original fingerprint involves image binarization, ridge thinning, and noise removal. Fingerprint Recognition using Minutiae Score Matching method is used for matching the minutiae points. Usually a technique called minutiae matching is used to be able to handle automatic fingerprint recognition with a computer system. In this literature review, nine papers are explored and an insight is obtained regarding different methods. References: [1] Weiguo Sheng, Gareth Howells, Michael Fairhurst, and Farzin Deravi,(2007), â€Å"A Memetic Fingerprint Matching Algorithm†, IEEE Transactions On Information Forensics And Security. [2] Aparecido Nilceu Marana and Anil K. Jain, (2005), â€Å"Ridge-Based Fingerprint Matching Using Hough Transform†, IEEE Computer Graphics and Image Processing, 18th Brazilian Symposium pp. 112-119. [3] Koichi Ito, Ayumi Morita, Takafumi Aoki, Tatsuo Higuchi, Hiroshi Nakajima, and Koji Kobayashi, (2005), â€Å"A Fingerprint Recognition Algorithm using Phase-Based Image Matching for low quality fingerprints†, IEEE International Conference on Image Processing, Vol. 2, pp. 33-36. [4] Kai Cao, Yang, X., Tao, X., Zhang, Y., Tian, J. ,(2009), â€Å"A novel matching algorithm for distorted fingerprints based on penalized quadratic model†, IEEE 3rd International Conference on Biometrics: Theory, Applications, and Systems, pp. 1-5. [5] Anil K. Jain and Jianjiang Feng, (2011), â€Å"Latent Fingerprint Matching†, IEEE Transactions On Pattern Analysis And Machine Intelligence, Vol. 33, No. 1, pp. 88-100. [6] Unsang Park, Sharath Pankanti, A. K. Jain, (2008), â€Å"Fingerprint Verification Using SIFT Features†, SPIE Defense and Security Symposium, Orlando, Florida, pp. 69440K-69440K. [7] Anil Jain, Yi Chen, and Meltem Demirkus, (2007), â€Å"Pores and Ridges: High-Resolution Fingerprint Matching Using Level 3 Features†, IEEE Transactions On Pattern Analysis And Machine Intelligence, Vol. 29, No.1, pp. 15-27. [8] Mayank Vatsa, Richa Singh, Afzel Noore, Max M. Houck, (2008), â€Å"Quality-augmented fusion of level-2 and level-3 fingerprint information using DSm theory†, Sciencedirect International Journal of Approximate Reasoning 50, no. 1, pp. 51–61. [9] Haiyun Xu, Raymond N. J. Veldhuis, Asker M. Bazen, Tom A. M. Kevenaar, Ton A. H. M. Akkermans and Berk Gokberk ,(2009), â€Å"Fingerprint Verification Using Spectral Minutiae Representations†,IEEE Transactions On Information Forensics And Security, Vol. 4, No. 3,pp. 397-409. [10] Mayank Vatsa, Richa Singh, Afzel Noore and Sanjay K. Singh ,(2009),â€Å"Combining Pores and Ridges with Minutiae for Improved Fingerprint Verification†, Elsevier, Signal Processing 89, pp.2676–2685. [11] Jiang Li, Sergey Tulyakov and Venu Govindaraju, (2007), â€Å"Verifying Fingerprint Match by Local Correlation Methods†, First IEEE International Conference on Biometrics: Theory, Applications,and Systems, pp.1-5. [12] Xinjian Chen, Jie Tian, Xin Yang, and Yangyang Zhang, (2006), â€Å"An Algorithm for Distorted Fingerprint Matching Based on Local Triangle Feature Set†, IEEE Transactions On Information Forensics And Security, Vol. 1, No. 2, pp. 169-177. [13] Peng Shi, Jie Tian, Qi Su, and Xin Yang, (2007), â€Å"A Novel Fingerprint Matching Algorithm Based on Minutiae and Global Statistical Features†, First IEEE International Conference on Biometrics: Theory, Applications, and Systems, pp. 1-6. [14] Qijun Zhao, David Zhang, Lei Zhang and Nan Luo, (2010), â€Å"High resolution partial fingerprint alignment using pore–valley descriptors†, Pattern Recognition, Volume 43 Issue 3, pp. 1050- 1061. [15] Liu Wei-Chao and Guo Hong-tao ,(2014), † Occluded Fingerprint Recognition Algorithm Based on Multi Association Features Match â€Å", Journal Of Multimedia, Vol. 9, No. 7, pp. 910—917 [16] Asker M. Bazen, Gerben T.B. Verwaaijen, Sabih H. Gerez, Leo P.J. Veelenturf and Berend Jan van der Zwaag, (2000), A correlation-based fingerprint verification system , ProRISC 2000 Workshop