This paper introduces a novel fingerprint matching algorithm using both ridge features and the conventional minutiae feature to increase the recognition performance against nonlinear deformation in fingerprints. The proposed ridge features are composed of four elements: ridge count, ridge length, ridge curvature direction, and ridge type. These ridge features have some advantages in that they can represent the topology information in entire ridge patterns existing between two minutiae and are not changed by nonlinear deformation of the finger. For extracting ridge features, we also define the ridge-based coordinate system in a skeletonized image. With the proposed ridge features and conventional minutiae features (minutiae type, orientation, and position),we propose a novel matching scheme using a breadthfirst search to detect the matched minutiae pairs incrementally. Following that, the maximum score is computed and used as the final matching score of two fingerprints. Experiments were conducted for the FVC2002 and FVC2004 databases to compare the proposed method with the conventional minutiaebased method.The proposed method achieved higher matching scores. The limitations of commonly used separable extensions of onedimensional transforms, such as the Fourier and wavelet transforms, in capturing the geometry of image edges are well known. In this paper, we pursue a Ã¢ÂÂtrueÃ´ÂÂÂ two dimensional transform that can capture the intrinsic geometrical structure that is key in visual information. The main challenge in exploring geometry in images comes from the discrete nature of the data. Thus, unlike other approaches, such as curvelets, that first develop a transform in the continuous domain and then discretize for sampled data, our approach starts with a discrete-domain construction and then studies its convergence to an expansion in the continuous domain. Specifically, we construct a discrete domain multi resolution and multi direction expansion using non-separable filter banks, in much the same way that wavelets were derived from filter banks. This construction results in a flexible multi resolution, local, and directional image expansion using contour segments, and thus it is named the contourlet transform. Thus, we conclude that the proposed ridge feature gives additional information for fingerprint matching with little increment in template size and can be used in conjunction with existing minutiae features to increase the accuracy and robustness of fingerprint recognition systems.
|Breadth first search, ridge count, ridge features, ridge-based coordinate system, sparse representation,
wavelets, contourlets, filter banks, multi resolution, multidirection, contours, geometric image processing.
|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, ecommerce, 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.
|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. 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 (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. we introduce and analyze the proposed ridge features
extracted from the ridge-based coordinate system .we introduce a fingerprint matching algorithm incorporating
conventional minutiae and the proposed ridge features.For image compression or content-based image retrieval, the use
of an efficient representation implies the compactness of the compressed file or the index entry for each image in the
database For practical applications, such an efficient representation has to be obtained by structured transforms and fast
algorithms . Natural images contain intrinsic geometrical structures that are key features in visual information This
result supports the hypothesis that the human visual system has been tuned so as to capture the essential information of
a natural scene using a least number of visual active cells. More importantly, this result suggests that for a
computational image representation to be efficient, it should based on a local, directional, and multi resolution
expansion. our approach starts with a discrete-domain construction and then studies its convergence to an expansion in
the continuous domain. The outline of the rest of the paper is as follows. After reviewing, we propose a multi resolution
and multi direction image expansion using non-separable filter banks. This construction results in a flexible multi
resolution, local, and directional image expansion using contour segments, and thus it is named the contourlet
FINGERPRINT PREPROCESSING AND RIDGE FEATURE EXTRACTION
A. Fingerprint Preprocessing
|Before extracting the proposed ridge features, we need to perform some preprocessing steps (see Fig. 2). 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 regions in the image.
|We then apply the method described 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 orientation is accurately or to extract the thinned ridge patterns consistently. Therefore, to detect
regions which have large curvature, we apply circular variance estimation . In our experiments, we use eight
neighboring blocks. Quality estimation and circular variance 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 short ridges and bridges. We can then extract the ridge structures consistently against various
B.Ridge Feature Extraction:
|We proposed a double filter bank structure for obtaining sparse expansions for typical images having smooth contours.
In this double filter bank, the Laplacian pyramid is first used to capture the point discontinuities, and then followed by a
directional filter bank to link point discontinuities into linear structures. The overall result is an image expansion using
basic elements like contour segments, and thus are named contourlets. In particular, contourlets have elongated
supports at various scales, directions, and aspect ratios. This allows contourlets to efficiently approximate a smooth
contour at multiple resolutions. In the frequency domain, the contourlet transform provides a multiscale and directional
|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 neighbourhood 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 .
Neighbourhoods are matched by dynamic programming and a match of local neighbourhoods 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 neighbourhood. Moreover,
the data structure of the ridge-based coordinate system is very similar to the -plet structure proposed in. 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) 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 ridge based coordinates are compared one by one and a similarity score is computed for
the dynamic programming.
|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). Fig.4 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
|Fig. 5. shows an example of matched minutiae using the proposed method. As shown in the figure, 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. The overlapped regions are where two fingerprints intersect after the linear transformation
(translation and rotation) using the matched minutiae.
EXPERIMENTAL RESULTS AND ANALYSIS
|We compared the recognition performances of two algorithms (the conventional minutiae-based matching method and
the proposed method). To demonstrate the effect of the proposed ridge features more generally, we chose the
conventional minutiae-based method, which is based on popular minutiae features such as minutiae position, minutiae
orientation, and minutiae type instead of the state-of-the-art minutiae-based algorithms which use additional specific
matching techniques.The conventional method utilizes several reference points for local alignment and an adaptive
tolerance box is used to calculate the number of matched minutiae
|For the experiments, we used the databases FVC 2002 DB1, DB2, DB3, and FVC 2004 DB1, released on the Web .
Regarding fingerprint quality, FVC 2002 DB3 and FVC 2004 DB1 have lower quality fingerprints than other databases
because the users were explicitly requested to exaggerate distortions. Therefore, it is reasonable to analyze the
robustness of the proposed method against skin distortions by using these databases. Each database is composed of 800
fingerprint images from 100 different fingers (eight impressions per finger). For genuine matches, each impression of
each finger is compared with other impressions of the same finger. Therefore, 2800 genuine matches were executed in
each database. For imposter matches, each impression of each finger is compared with all impressions of the different
fingers. Therefore, 316 800 imposter matches were conducted in each database. Table I shows the equal error rate
(EER) comparisons of two matching methods on the FVC databases and Fig. 11 shows the ROC curves on each
database. From the experimental results, we can see that the proposed method is superior to the conventional minutiaebased
one for all the databases. Even though the performances for FVC 2002 DB3 and FVC 2004 DB1 are lower than
those for FVC 2002 DB1 and DB2, we can maintain that our ridge features can support the minutiae features when they are used together in the matching stage. Some recognition errors occurred and can be analyzed in the following way.
The first cause is a wrongly estimated orientation error the vertical axis starting from a minutia (red-circle) is slightly
tilted towards the vertical axis determined from the corresponding minutia, since the orientation fields are poorly
estimated. As a result, there is a large variation between the ridge length (rl) features in the corresponding sets.
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. In 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.
A. Wavelets vs. Contourlets
|To highlight the difference between the wavelet and contourlet transform, Figure 14 shows a few wavelet and
contourlet basis images. We see that contourlets offer a much richer set of directions and shapes, and thus they are
more effective in capturing smooth contours and geometric structures in images. Next we compare the nonlinear
approximation (NLA) performancesof the wavelet and contourlet transforms. In these NLA experiments, for a given value M, we
select the Mmost significant coefficients in each transform domain, and then compare the reconstructed images from
these sets of M coefficients. Since the two transforms share the same detail subspaces, it is possible to restrict the
comparison in these subspaces. We expect that most of the refinement happens around the image edges. sequences of
nonlinear approximated images at the finest detailed subspace Wj using the wavelet and the contourlet transforms,
respectively, for the input Peppers image. The wavelet scheme is seen to slowly capture contours by isolated ―dots.
By contrast, the contourlet scheme quickly refines by well-adapted ―sketches, in much the same way as the new
scheme shown in Figure 2. Contourlets are shown to be superior compared to wavelets in capturing fine contours (e.g.,
directional textures on cloths). In addition, there is a significant gain of 1.46 dB in peak signal-to noise ratio (PSNR)
|The improvement in approximation by contourlets based on keeping the most significant coefficients will directly lead
to improvements in applications, including compression, denoising, and feature extraction. As an example, for image
denoising, random noise will generate significant wavelet coefficients just like true edges, but is less likely to generate
significant contourlet coefficients. Consequently, a simple thresholding scheme applied on the contourlet transform is
more effective in removing the noise than it is for the wavelet transform.
CONCLUSIONS AND SUGGESTIONS 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
minutiae-based one. we developed a new filter bank structure, the contourlet filter bank, that can provide a flexible
multiscale and directional decomposition for images. The developed discrete filter bank has a precise connection with
the associated continuous domain contourlet expansion. This connection is defined via a directional multiresolution
analysis that provides successive refinements at both spatial and directional resolution. With parabolic scaling and
sufficient directional vanishing moments, the contourlet expansion is shown to achieve the optimal approximation rate
for piecewise C2 smooth images with C2 smooth contours. Experiments with real images indicate the potential of
contourlets in several image processing applications. A Matlab contourlet toolbox is freely available for download from
the MatlabCentral www.mathworks.com/matlabcentral).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
Tables at a glance
Figures at a glance
- IEEETRANSACTIONS ON INFORMATION FORENSICS AND SECURITY, VOL. 6, NO. 2, JUNE 2011 Fingerprint Matching IncorporatingRidge Features With Minutiae Heeseung Choi, Kyoungtaek Choi, and Jaihie Kim
- IEEE TRANSACTIONS ON IMAGE PROCESSING 1 The Contourlet Transform: An Efficient Directional Multiresolution ImageRepresentation Minh N. Do, Member, IEEE, and Martin Vetterli, Fellow, IEEE 3K. Choi, H. Choi, S. Lee, and J. Kim,
- Fingerprint image mosaicking by recursive ridge mapping, Special Issue Recent Adv. Biometrics Syst., IEEE Trans. Syst., Man, Cybern. B,Cybern., vol. 37, no. 5, pp. 1191–1203, Oct. 2007
- S. Chikkerur, A. N. Cartwright, and V. Govindaraju, ―K-plet and coupled BFS: A graph based fingerprint representation and matchingalgorithm, Notes Comput. Sci., Adv. Biometrics, vol. 3832, pp.309–315, 2005. S. Theodoridis and K. Koutroumbas, Pattern Recognit., 3rd ed. San Diego, CA: Academic, 2006.
- M. B. Wakin, J. K. Romberg, H. Choi, and R. G. Baraniuk, ―Ratedistortionoptimized image compression using wedgelets, in Proc. IEEE Int. Conf. on Image Proc., Rochester, New York, Oct. 2002.
- R. Shukla, P. L. Dragotti, M. N. Do, and M. Vetterli, ―Rate-distortion optimized treestructured compression algorithms for piecewise smooth images, IEEE Trans. Image Proc., vol. 14, pp. 343–359, Mar. 2005.
- D. D.-Y. Po and M. N. Do, ―Directionalmultiscale modeling of imagesusing the contourlet transform, IEEE Trans. Image Proc., to appear,http://www.ifp.uiuc.edu/˜minhdo/publications.
- Z. M. Kovacs-Vajna, ―A fingerprint verification system based on triangular matching and dynamic time warping, IEEE Trans. PatternAnal.Mach. Intell., vol. 22, no. 11, pp. 1266–1276, Nov. 2000.