Keywords
|
| Breadth first search, ridge count, ridge features and Ridge based coordinate system. |
I. INTRODUCTION
|
| Fingerprint recognition has been widely adopted for user identification due to its reliable performance, usability, and low cost compared with other biometrics such as signature, iris, face, and gait recognition. It is used in a wide range of forensic and commercial applications, e.g., criminal investigation, e-commerce, and electronic personal ID cards. Although significant improvement in fingerprint recognition has been achieved, many challenging tasks still remain. Among them, nonlinear distortions, presented in touch based fingerprint sensing, make fingerprint matching more difficult. As shown in Fig. 1, even though these two fingerprint images are from the same individual, the relative positions of the minutiae are very different due to skin distortions. This distortion is an inevitable problem since it is usually associated with several parameters, including skin elasticity, non uniform pressure applied by the subject, different finger placement with the sensor, etc. |
| To deal with the distortions in fingerprint images and improve the matching performance, various methods have been proposed by many researchers. These can be roughly classified into several groups: modeling the distortion of fingerprints; detecting the distortions using special hardware or video sequences; allowing some amount of distortion in the minutiae matching stages; and using local similarity measure. Cappelli et al. proposed a plastic distortion model of a finger print to calculate the nonlinear deformation of fingerprints. They first defined three distinct regions in fingerprint images and described the distortion mechanism using some distortion parameters. This method has successfully been applied to the generation of synthetic fingerprints of the same finger. However, it is hard to estimate the parameters accurately due to insufficient information. Bazen et al. and Ross et al. used the thin plate spline (TPS) model to compensate for deformations, but this sort of alignment process typically requires too much computational power to be used in practical fingerprint recognition systems. Ratha et al. proposed a method to directly measure the forces and torques on the scanner using special hardware and Dorai et al. estimated the distortions by observing fingerprint video sequences. These two methods prevent the capture of severely distorted images, but they cannot detect the distortion in data sets that were collected in the past and the need of additional hardware restricts their use in practical situations. Luo et al. used changeable tolerance boxes in the minutiae matching process. |
| The size of the tolerance boxes is incrementally increased, moving from the center towards the borders of the fingerprint area, to deal with the effect of distortion. Lee et al. applied distance normalization and local alignment during minutiae matching. In local minutiae matching, these approaches can be considered as an effective tool. However, as the size of the tolerance boxes had to be increased, the probability of falsely matching fingerprints from different fingers also increases. Some methods used local similarity measures to improve the robustness of the distortions since fingerprint images are less affected by distortions in the local area. Jiang et al. proposed a method using the similarity measure defined between local structural features to align fingerprint images. Kovacs Vajna proposed a method using triangular matching by checking the correspondence of gray scale profiles between every pair of minutiae from the template and the corresponding positions in the input images. And the dynamic time warping method was used to tolerate small location errors of features. |
| However, for widespread use of these approaches, a consolidation step may be implemented to check whether the local similarity holds at the global level. Moreover, although many fingerprint matching methods have been developed to cope with distortions, most of them are minutiae based. Thus, they cannot use more topological information (such as ridge shape) covering the entire fingerprint image and the limitation of information still exists. In addition, these methods use complex data structures and many parameters for fingerprint matching. Accordingly, it is hard to understand and implement these methods accurately. Considering the facts mentioned above, instead of developing complex distortion models or elaborates minutiae alignment algorithms, we propose a new and simple matching scheme by incorporating conventional minutiae features and additional ridge features associated with corresponding minutiae sets. |
| To extract the ridge features, a ridge-based coordinate system is also defined. The ridge features consist of four elements: ridge count (rc), ridge length (rl), ridge curvature direction (rcd), and ridge type (rt). These features are invariant to any geometric transformations (rotation, translation) of the fingerprints and concisely represent the relationships between the minutiae since the maintenance of ridge structures is robust to distortions. Moreover, since the correlation between the proposed ridge features and conventional minutiae features is low, combining these features leads to an improvement in the overall recognition performance with a small increment in template size. Our ridge features require only 5 bytes (ridge count-1 byte; ridge length-2 bytes; ridge curvature direction-1 byte; and ridge type-1 byte) for each minutiae pair. This paper is organized as follows. In first Section, we introduce and analyze the proposed ridge features extracted from the ridge-based coordinate system. Then, we introduce a fingerprint matching algorithm incorporating conventional minutiae and the proposed ridge features. |
II. FINGERPRINT PREPROCESSING AND RIDGE FEATURE EXTRACTION
|
Fingerprint Preprocessing
|
| Before extracting the proposed ridge features, we need to perform some preprocessing steps These steps include typical feature extraction procedures as well as additional procedures for quality estimation and circular variance estimation. We first divide the image into 8x8 pixel blocks. Then, the mean and variance values of each block are calculated to segment the fingerprint regions in the image. We then apply the method to estimate the ridge orientation and the ridge frequency is calculated. The Gabor filter is applied to enhance the image and obtain a skeletonized ridge image. Then, the minutiae (end points and bifurcations) are detected in the skeletonized image. We then apply the method to estimate the ridge orientation and the ridge frequency is calculated. |
| The Gabor filter is applied to enhance the image and obtain a skeletonized ridge image. Then, the minutiae (end points and bifurcations) are detected in the skeletonized image. The quality estimation procedure is performed in order to avoid extracting false minutiae from poor quality regions and to enhance the confidence level of the extracted minutiae set. Furthermore, in regions where ridge flows change rapidly, such as the area around a singular point, it is hard to estimate the ridge orientations accurately or to extract the thinned ridge patterns consistently. Therefore, to detect regions which have large curvature, we apply circular variance estimation. The circular variance of the ridge flows in a given block is calculated. Here, we use eight neighboring blocks. Quality estimation and circular variance values are used to avoid generating feature vectors in poor quality regions or in regions around singular points. Moreover, we adopt some post processing steps to remove falsely extracted ridges, such as sources. |
Ridge Feature Extraction
|
1) Proposed Ridge-Based Coordinate System
|
| After performing the preprocessing steps, we obtain the skeletonized ridges and minutiae information from the fingerprint image. We can then define ridge coordinates and extract ridge features between two minutiae. Each ridge-based coordinate system is defined by a minutia (called origin) and vertical and horizontal axes starting from the origin minutia. First, the vertical axis is defined by drawing a line passing through the origin and orthogonal to the orientation of the origin. The axis also traverses the ridge flows orthogonally. In addition, to define the sign of the vertical axis according to the origin, the cross product between the orientation of the origin and the vector pointing from the origin to the side of the vertical axis is calculated. We determine the positive and the negative side of the vertical axis by checking the sign value. To represent the relative position of the minutiae according to the origin, horizontal axes should be defined. |
| The horizontal axes are defined as ridges intersecting the vertical axis. To define the sign of each horizontal axis, the cross product between the vectors pointing from the intersection to the vertical and horizontal axes is calculated. The vector pointing from the intersection to the horizontal and the vertical axis, respectively. It includes four components such as the ridge count, ridge length, ridge curvature direction, and ridge type, respectively. These four components form a ridge-based feature vector between two minutiae and this feature vector is used in the matching process. In the following sections, we will explain in detail these ridge features were selected and the methods for extracting these features. |
| 2) Ridge Feature Extraction: In the general ridge count methods, the number of ridges that intersect the straight line between two minutiae in the spatial domain is counted. However, when the ridge-counting line is parallel to the ridge structures, the line may meet the same ridge at one point, at more than two points, or at no point, due to skin deformation. Therefore, unlike existing ridge-counting methods, here, the ridge count (rc) is calculated by counting the number of ridges along the vertical axis until the axis meets the ridge attached to the neighboring minutia. The vertical axis is perpendicular to the ridge structures. |
| Thus, the counted numbers are less affected by skin deformation than in the results of the general ridge counting methods. In order to prove the effectiveness of the proposed ridge counting method, we used 50 fingers from FVC 2002 DB1-A and manually paired the corresponding minutiae among the five images from each finger.After pairing two corresponding minutiae, we estimated the probability distributions of the absolute difference of the ridge counting numbers in each method. It shows that the absolute difference of the ridge counting numbers using our method is smaller than that using the conventional ridge count method. Therefore, we can conclude that our ridge count feature is more robust to skin deformation. Furthermore, to increase the discriminating power of the ridge count (rc) feature, we also consider the direction of the ridge countl ine. The ridge count (rc) is not always a positive number and the sign of the ridge count follows the sign of the vertical axis. If two minutiae are directly connected by the same ridge, the ridge count would be zero. The ridge length (rl) is the distance on the horizontal axis from the intersection of the vertical and horizontal axis to a minutia. To prove the usefulness of the ridge length feature, we conducted an experiment similar to the analysis of the ridge count feature. It shows the probability distribution of the absolute difference of the ridge length feature. The absolute differences of ridge length elements are mostly less than 16 pixels. Therefore, we can set the threshold of the ridge length feature to determine the same fingerprint as 16 pixels. The ridge length value also has a sign and follows the sign of the related horizontal axis to improve the discriminating power. |
| To use more topology information in ridge patterns for matching, the ridge curvature direction is also considered. Even though the ridge count and ridge length values are very similar, the shapes of the ridge patterns may be different. The ridge curvature direction is defined and it represents the vector between the sampling points along the horizontal axis from the intersection of the vertical and horizontal axes to the minutia and represents the number of sampling points. In our experiment, we set the sampling point every 8 pixels on the ridges. Then, by checking the sign of this value, we can determine the ridge curvature direction. The ridge curvature direction feature is robust to skin deformation but some errors may still occur. First, ridges may have more than two inflection points, which makes it hard to define this feature. Second, some ridges are too straight to define a curved direction. and vice versa. Therefore, considering these facts and to further improve the discriminating power of ridge features, the ridge type (rt) is used as one of the ridge features instead of a minutia type. To determine the ridge type (rt), each minutia is first classified as an end point or a bifurcation. If a minutia is an end point, there is only one ridge belonging to the minutia. If a minutia is a bifurcation, there are three ridges connected to the minutiae. Next, the type of ridge associated with the minutia is determined as one of four types according to the type of the minutia and the relative position of the ridges. If a minutia is an end point, the ridge type is defined as In a bifurcation case, the three ridges are labeled by checking the angle between each ridge and the minutia orientation. |
| A triangle is created by three points on the ridges (equidistant from the bifurcation). If the vertex of the triangle is not on the shortest side of the triangle, then the ridge belongs to the vertex and is defined as type. The other two ridges are classified as type and, moving in a clockwise direction from. Generally speaking, ridge type can change only into ridge type or. However, type cannot be converted into type. Therefore, we use this information in the fingerprint matching. |
| The overall procedure for extracting ridge features is as follows: |
| 1) Perform preprocessing steps and extract a ridge image from a fingerprint. |
| 2) Traverse the ridge-valley structures along the vertical axis from each minutia origin. |
| a) If the vertical axis intersects with the ridges attached to a minutia, extract ridge features (ridge count, ridge length, ridge curvature direction, and ridge type) from the origin to the minutia and form a ridge feature vector between the origin and the minutiae. |
| b) Keep traversing all the ridges until one of three terminating conditions is satisfied (see below). |
| 3) If all minutiae are used as the origin minutiae, terminate the procedure. Otherwise, return to step 2). |
| The termination conditions include the following three cases: |
| 1) The vertical axis reaches a background region in the fingerprint image. |
| 2) The vertical axis reaches a poor quality region in the fingerprint image. |
| 3) The vertical axis reaches a high circular variance region in the fingerprint image. |
III. FINGERPRINT MATCHING
|
| The ridge feature vectors between the minutiae in the ridge coordinate system can be expressed as a directional graph whose nodes are minutiae and whose edges are ridge feature vectors. Thus, we can adopt graph matching methods to utilize the ridge feature vectors in fingerprint matching. Chikkerur et al. proposed a graph-based fingerprint minutiae matching method in a Euclidean space. They first defined the local neighborhood of each minutia, called plet, which consists of the nearest minutiae from a center minutia. |
| The comparison of two plets is performed by computing the distance between the two strings obtained by concatenating the neighboring minutiae, sorted by their radial distance with respect to the center minutia. Neighborhoods are matched by dynamic programming and a match of local neighborhoods is propagated with a breadth-first fashion. |
| Thus, we apply this matching scheme to our ridge-based coordinate system, since the ridge-based coordinate system can be represented as a graph and each coordinate system makes a local neighborhood. Moreover, the data structure of the ridge-based coordinate system is very similar to the plet structure. |
| The overall flow of the proposed fingerprint matching algorithm is as follows: 1) Initially match any pair of ridge based coordinate systems extracted from the enrolled fingerprint image and the input fingerprint image using dynamic programming. 2) Select the top degree of matched ridge-based coordinate pairs. 3) For every initially matched pair, a breadth-first search (BFS) is performed to detect the matched ridge-based coordinate pairs incrementally. 4) Check the validity of the matched coordinate pairs using the relative position and orientation of the minutiae and count the number of matched minutiae. 5) Iterate steps 3 and 4 N times and then return the maximum number of matched minutiae. 6) Compute the matching score. Dynamic programming is applied to find the optimal solution in matching two string sequences in the enrolled and input ridge-based coordinates. The ridge feature vectors in a ridge-based coordinate system are arranged in the order of their ridge count feature component (rc), then the order is invariant intrinsically. Therefore, the feature vectors in a ridge-based coordinate system can be stored as the elements of an ordered sequence. Thus, all the enrolled and input ridgebased coordinates are compared one by one and a similarity score is computed for the dynamic programming. The similarity score is based on the Bayesian decision rule and is calculated: otherwise the absolute difference between two feature vectors, is the correctly matched class, and is the incorrectly matched class. In order to calculate the posterior probability, we assumed that the prior probabilities of and are equal. |
| For the ridge feature vector, the three feature elements (ridge count, ridge length, and ridge curvature direction) are used to calculate the scores and the ridge type feature is used to check the validity of the candidate pairs. After that, we select the top degree of matched ridge-based coordinate pairs. In this paper, we set the value as 10. For every initially matched pair, we perform a BFS to increment the match for other neighboring ridge-coordinate systems. However, there is not always a path for every minutiae pair because we do not extract ridge features in the fingerprint regions which have low quality or a high curvature. |
| Therefore, we find a detour path to perform the BFS. For example, even if it is not possible to directly extract the ridge feature vector between minutia and due to the absence of a path, it is still possible to obtain the ridge feature vector by including minutia (as). It shows some examples of the corresponding ridge feature vectors using the detour, as the number of connection steps increases. We check the validity of the matched coordinate pairs using the relative position and orientation of the minutiae used in conventional minutiae-based matching. If the relative position and orientation of the minutiae in the coordinate pair are also matched, we can be sure that these minutiae are correctly matched. |
| We then count the number of matched minutiae and store them. Finally, after the execution of the BFS procedure for every initial matched pair, we find the maximum number of matched minutiae between two fingerprints. It shows an example of matched minutiae using the proposed method. Even if two impressions of the same finger are different due to skin distortion, many minutiae are matched correctly. To compute the matching score, we must consider both the degree of overlap between two impressions and the degree of similarity of the overlapped region. Thus, the matching score can be computed.. The overlapped regions are where two fingerprints intersect after the linear transformation (translation and rotation) using the matched minutiae. |
| Therefore, by enhancing the orientation estimation process, the performance can be improved. Second, there are some minutiae pairs offering no ridge feature vectors because some images had small foreground regions or their levels of quality were too low. The foreground region was very small and there were few minutiae. |
| Moreover, only a few minutiae were located in the region (high circular variance region) around a singular point. The foreground region was split in two by a poor quality region, so there was no connection between the minutiae in the upper good quality region and those in the lower good quality region. This disturbed the generation of ridge feature vectors in the whole fingerprint region, reducing the discriminating power. And the experiments were conducted on a PC with Core2 Duo 2.4 GHz. The average matching time of the proposed method was 83 ms. |
IV.CONCLUSION AND SUGGESTION FOR FUTURE WORK
|
| In this paper, we proposed a novel fingerprint matching algorithm using both ridge features and the minutiae. The ridge features consist of four elements (ridge count, ridge length, ridge curvature direction, and ridge type) that describe the relationship between the minutiae. With the proposed ridge features and conventional minutiae features (minutiae type, orientation, and position), we proposed a novel matching scheme using a BFS to detect the matched minutiae pairs. The experimental results show that the proposed method gives higher matching scores compared to the conventional minutiaebased one. Hence we can conclude that the proposed ridge features give additional information for fingerprint matching with little increment of template size. |
| And, for future work, we will try to incorporate these features into the state-of-the-art minutiae-based matchers for further improvement of the matching performance. Also, our matching method needs to be improved for images with a small foreground area and those of low quality. Therefore, in future work, we will develop the use of global knowledge of fingerprints, such as singular point position, to enhance the matching accuracy. |
| We will also develop a robust reprocessing method to reduce enhancement errors. Moreover, our ridge features can be used in other applications. In the area of fingerprint identification, it is important to be able to extract alignment-free features since it needs no time to align a query feature set with the enrolled feature sets one by one. In cancelable fingerprints, without a fiducial corresponding pair such as a core point, it is difficult to align a transformed feature set with an enrolled one. The proposed ridge features are invariant to any transform, thus they can be used in addition to conventional alignment-free features in the fingerprint identification or cancellable fingerprint area. |
Figures at a glance
|
 |
 |
| Figure 1 |
Figure 2 |
|
| |
References
|
- D. Maltoni, D. Maio, A. K. Jain, and S. Prabhakar, Handbook of Fingerprint Recognition. New York: Springer-Verlag, 2003.
- Ross, S. Dass, and A. K. Jain, “A deformable model for fingerprint matching,” Pattern Recognit., vol. 38, no. 1, pp. 95– 103, 2005.
- X. Chen, J. Tian, X. Yang, and Y. Zhang, “An algorithm for distorted fingerprint matching based on local triangle feature set,” IEEE Trans.Inf. Forensics Security, vol. 1, no. 2, pp. 169–177, Jun. 2006.
- M. Bazen and S. H. Gerez, “Fingerprint matching by thin-plate spline modelling of elastic deformations,” Pattern Recognit., vol. 36, no. 8,pp. 1859–1867, Aug. 2003.
- X. P. Luo, J. Tian, and Y.Wu, “A minutia matching algorithm in fingerprint verification,” in Proc. 15th ICPR, Sep. 2000, vol. 4, pp. 833–836.
- X. Jiang and W. Y. Yau, “Fingerprint minutiae matching based on the local and global structures,” in Proc. 15th Int. Conf. Pattern Recognition,Barcelona, Spain, Sep. 2000, vol. 2, pp.1038-1041.
- Z. M. Kovacs-Vajna, “A fingerprint verification system based on triangular matching and dynamic time warping,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 22, no. 11, pp. 1266 1276, Nov. 2000.
- R. Cappelli, A. Erol, D. Maio, and D. Maltoni, “Synthetic fingerprint image generation,” in Proc. 15th Int. Conf. Pattern Recognition, Barcelona, Spain, Sep. 2000, pp. 3475-3478.
- Lee, S. Lee, J. Kim, and S. Kim, “Preprocessing of a fingerprint image captured with a mobile camera,” in Proc. IAPR Int. Conf. Biometrics (ICB), Hong Kong, Jan. 2006, pp. 348-355, Springer LNCS 3832.
- Maio and D. Maltoni, “Ridge-line density estimation in digital images,” in Proc. 14th ICPR, 1998, vol. 1, pp. 534-538.
- L. Hong, Y. Wan, and A. K. Jain, “Fingerprint image enhancement: Algorithm and performance evaluation,” IEEE Trans. Pattern Anal.Mach. Intell., vol. 20, no. 8, pp. 777-789, Aug. 1998
|
Menu