Subscribe Now Subscribe Today
Research Article
 

A Robust Correlation Based Fingerprint Matching Algorithm for Verification



Abdullah Cavusoglu and Salih Gorgunoglu
 
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail
ABSTRACT

In this study, we present a new correlation-based fingerprint verification algorithm which segments the image to start with, proceeds by determining the orientation fields then finds the Reference Point (RP) and finally normalizes it before the application of the suggested algorithm. In this study, instead of a single correlation value-as in standard template matching-the mean value of correlation factors (i.e., corresponding to the signatures which are obtained from certain radius distances from the RP) are calculated and compared. If it is over a certain threshold the result of the matching process is positive otherwise negative. The algorithm does not need the storage of the whole FI and helps reducing the required space for them. The experiments executed on FVC2000 have shown that, the suggested algorithm is successful not only on the good quality FI but also on the bad or poor quality FI. The algorithm is fast and robust providing accurate results in most of the times.

Services
Related Articles in ASCI
Similar Articles in this Journal
Search in Google Scholar
View Citation
Report Citation

 
  How to cite this article:

Abdullah Cavusoglu and Salih Gorgunoglu, 2007. A Robust Correlation Based Fingerprint Matching Algorithm for Verification. Journal of Applied Sciences, 7: 3286-3291.

DOI: 10.3923/jas.2007.3286.3291

URL: https://scialert.net/abstract/?doi=jas.2007.3286.3291

INTRODUCTION

Comparison of two Fingerprint Images (FI) is probably the most important stage of the fingerprint verification process. Such systems work with the following principle; initially a fingerprint image is presented to the system then a database search is conducted on the systems fingerprint images stored earlier. The output of such a system is either a positive answer stating that the presented ID corresponds to the same person providing the fingerprint or vice versa (Jain et al., 1997, 2004). Generally, the fingerprint matching algorithms may be classified as: minutiae-based, ridge feature-based and correlation based (Maltoni et al., 2003). The minutiae based systems extracts the minutiae points (i.e., ridge ending, bifurcation) and their direction in respect to the reference point. In such systems the important point is determination of these points reliably. Therefore, especially in the case of poor quality images an enhancement is required (ÇavuŞoImage for - A Robust Correlation Based Fingerprint Matching Algorithm for Verificationlu and GörgünoImage for - A Robust Correlation Based Fingerprint Matching Algorithm for Verificationlu, 2006; Hong et al., 1998). For a reliable matching the preprocessing steps, finding the orientation of the image (Bazen and Gerez, 2002), segmentation (Mehtre and Chatterjee, 1989), reference point detection (Wang and Wang, 2004), binarization (Liao et al., 2001), thinning (Espinosa-Duro, 2003), determining the minutiae points (Shi and Govindaraju, 2006) and the post-processing stage such as elimination of the false minutiae points are required (Tico and Kuosmanen, 2000).

The ridge feature based fingerprint identification systems are generally applied on the poor quality FI. This is due to the difficult nature of the feature extraction process in such FIs. On the other hand, the other features of the FIs-local ridge directions, frequencies, ridge shapes and texture information-may be obtained more reliably when compared to the minutiae based approach (Jain et al., 2000; Patil et al., 2005).

The correlation based analysis; a direct matching between the two FIs is attempted. To do that, the images are superimposed and displacements and correlations of the rotations of the relevant sections are calculated. The maximum level of the correlation factor is interpreted as the matching sections for the images. In other words, the correlation value is the resemblance factor between the two images.

In the literature a number of correlation based algorithms may be found. Rusyn et al. (2002) used the spectral information obtained from the FIs in correlation, while Hatano et al. (2002), uses differential correlation computed as the difference between the maximum and minimum correlations. And Bazen and Gerez (2000), takes a certain distinctive parts of the template image and search for them on the query image. However this approach requires template selection process for each FI increasing the time required for the process.

In this study, we are proposing a new straightforward algorithm based on the correlation approach. The algorithm neither requires a template selection such as in Bazen et al. (2000), nor subdivision of the FIs into smaller windows along with a thinning process on the image Hatano et al. (2002), also increasing the computational time.

THE CORRELATION BASED MATCHING ALGORITHM

The suggested algorithm requires 5 steps; segmentation of the image, determination of ridge orientations, RP detection, normalization of the images and finally the proposed algorithm.

Segmentation: It is a process of removing the unnecessary sections of the image where the actual fingerprint image is enclosed. Therefore for the relevant sections of the image, no time is spent for preprocessing steps. This operation may be based on the variance of the gray-scale intensities and the local directional histogram values, gradient coherence values (Mehtre and Chatterjee, 1989). In this application a variance based segmentation operation (Jain et al., 1997) calculated by:

Image for - A Robust Correlation Based Fingerprint Matching Algorithm for Verification
(1)

Image for - A Robust Correlation Based Fingerprint Matching Algorithm for Verification
(2)

is used, where the w is the block size, M(x, y) and σ(x, y) are the mean intensity value and variance of the block centered at (x, y).

Ridge orientation: The ridge directions are used for determining the RP. The term orientation image often refers to the determination of local ridge orientation in the FI. The following processing steps are applied for finding orientations (Hong et al., 1998). The local orientation of the (x, y) centered wxw sized block is calculated by:

Image for - A Robust Correlation Based Fingerprint Matching Algorithm for Verification
(3)

Image for - A Robust Correlation Based Fingerprint Matching Algorithm for Verification
(4)

Image for - A Robust Correlation Based Fingerprint Matching Algorithm for Verification
(5)

Image for - A Robust Correlation Based Fingerprint Matching Algorithm for Verification
Fig. 1: Regions of integration of the sine components and detected RP

Where, the ∂x(x, y) and ∂y (x, y) are calculated by using sobel operators. Following the orientation fields are smoothed by a low pass filter.

Determining the RP: To be able to align two FI, a RP is required. The most widely used RP is the core point. In our application we have used the algorithm presented in (Wang and Wang, 2004). It is based on differential sum of sine values of the directions of the pixels that are located on a certain radius (Fig. 1).

Normalization: To reduce the effect of the fingerprint pressure differences and sensor noise normalization is performed. It is a pixel based operation which does not chance the clarity of the ridge and valley tracks on the fingerprint. It is performed on the subdivided image blocks. After calculating the mean and standard deviation of the blocks corresponding new pixel colors are obtained. If this operation is performed on the entire image rather than the subdivided blocks, the system can not compensate the intensity variations caused by the fingerprint pressure differences. The normalized pixel value (i.e., within the block) is calculated by Eq. 6 using the sigmoid function:

Image for - A Robust Correlation Based Fingerprint Matching Algorithm for Verification
(6)

Correlation algorithm: The correlation based analysis of the fingerprints is based on the aligned images where the gray-scale intensities are used. The cross correlation operation gives us the similarity percentage of the two images. The disadvantages of using correlation in fingerprint matching are expressed by Maltoni et al. (2003) as:

The non-linear distortions, different pressures on the same fingerprint cause important global differences on the FI.

The differences on the skin conditions and the contrast on the fingerprint and ridge thicknesses produce important diversities.

Direct application of cross correlation is computationally very expensive.

In addition in the case of correlation based analysis the storage cost of the template FI is approximately 90 KB (i.e., 300χ300 pixel, in TIF format). While in our application, as will be described in detail, this requirement is approximately 5 KB. With the proposed algorithm, the first two disadvantages listed above are partially eliminated by using the mean value of a 3χ3 mask of pixels-instead of taking gray-scale intensity of each pixel-and normalization operation. The most important structural difference between the ordinary image and FIs is that there are ridges and valleys in the latter one. Furthermore, a RP is determined in such images. Therefore, the best point where the two images best aligned is the narrow area around the RP (i.e., not the whole image). Calculation of the correlation around the RP reduces time cost dramatically. Another important factor is the determination of digital signatures to be used in correlation. They must give the distinctions between the two images. The details of the sequence of the algorithm are as follows:

The segmentation, smoothed directional image, RP determination and normalization on both the input and template image are accomplished.

The set of digital signatures are formed by means of Eq. 7 and 8 which correspond to the set of points of the various radius values on the normalized input and template FI.

Image for - A Robust Correlation Based Fingerprint Matching Algorithm for Verification
(7)

Image for - A Robust Correlation Based Fingerprint Matching Algorithm for Verification
(8)

Where,xt, yt, xm, ym represents the RP coordinates of the template and input FIs, respectively, while r, θ corresponds to the radius and angular values and finally, Image for - A Robust Correlation Based Fingerprint Matching Algorithm for Verificationstands for the set of digital signatures obtained from the values with the r radius and θ angle from the xt, yt RP of the template image. Figure 2 shows the acquirement of the feature vectors of both the template and input images.

Image for - A Robust Correlation Based Fingerprint Matching Algorithm for Verification
Fig. 2: Driving the feature vectors of the normalized template and input FI

By taking the RP as the reference, a block of the size wxw (e.g., 20χ20) is taken, then by shifting the RP, the differential sum of the square of the digital signatures of both images-for different placements-are calculated. The best matching point for the images-as Eq. 9 gives-is where the sum of squared differences are minimum. The coordinate values of this point are saved to be used in the next step.

Image for - A Robust Correlation Based Fingerprint Matching Algorithm for Verification
(9)

The digital signatures of the input image are obtained by rotating the image by Δθ = [–15°, 15°] with the incremental steps of 1°. Following, for each rotation, the normalized cross correlation values of both images are calculated using Eq. 10.

Image for - A Robust Correlation Based Fingerprint Matching Algorithm for Verification
(10)

Here, for each rotation value, 12 different correlations are obtained. The mean value of which is calculated by Eq. 11. The maximum correlation value within this set is then used to determine the matching score of the images.

Image for - A Robust Correlation Based Fingerprint Matching Algorithm for Verification
(11)

EXPERIMENTAL RESULTS

The experiments are executed on FVC2000 database. The experimental results show that determination of the RP is very important. In the case of low quality images this is rather difficult. Therefore the best performing algorithm must be used. In Fig. 3 a good quality template and inputs FIs along with selected signatures (i.e., from 12) are illustrated. As it may be observed, due to the correct determination of RP the mean correlation value is high as Table 1 presents. Determining FP correctly provides high performance accuracy for the suggested algorithm. However in the opposite cases this level decreases. Figure 4 presents False Matching Rate (FMR) and False Non-Matching Rate (FNMR) curves.

Image for - A Robust Correlation Based Fingerprint Matching Algorithm for Verification
Fig. 3: Good quality template and input FI (first row) and their corresponding selected signatures and cross correlations (second row)

Table 1: Execution times of matching algorithm (on P4 2.8 MHz PC with 512 MB RAM and WinXP OS, FVC2000 Db1_a)
Image for - A Robust Correlation Based Fingerprint Matching Algorithm for Verification

Image for - A Robust Correlation Based Fingerprint Matching Algorithm for Verification
Fig. 4: False Matching Rate (FMR) and False Non-Matching Rate (FNMR)

Optimization of the orientation image and RP detection algorithms dramatically affects the system performance. We are therefore currently working on these algorithms.

CONCLUSIONS

Minutiae based fingerprint matching requires preprocessing steps. These steps cause either changes or total loss of important information on the FI. Especially, in the case of poor quality images acquiring them reliably becomes more difficult. Depending on the quality of the FI several false minutiae may come out. However, these FI may still contain valuable information which may reverse this false selection. In this study, a new correlation based approach is presented. The algorithm takes both the input and template images and calculates 12 different cross correlations based on certain radius values from RP and finds a total sum, which in turn used as the determination factor whether the images correspond to the same fingerprint. In addition the algorithm requires lesser storage for the template images, by storing only the important fraction of the image rather then the whole image-when compared to the conventional approaches. Since the algorithm accomplishes its target with minimum number of preprocessing steps, the error level is lesser. And it is fast due to its basic nature and confinement of the analysis into a narrow area. The algorithm performs better than the minutiae based approaches especially in the case of poor quality FI.

REFERENCES
1:  Bazen, A.M., G.T.B. Verwaaijen, S.H. Gerez, L.P.J. Veelenturf and B.J. van der Zwaag, 2000. A correlation-based fingerprint verification system. Proceedings of the Workshop on Circuits Systems and Signal Processing, October 18, 2000, EEMCS EPrints Service, pp: 205-213.

2:  Bazen, A.M. and S.H. Gerez, 2002. Systematic methods for the computation of the directional fields and singular points of fingerprints, pattern analysis and machine intelligence. IEEE Trans., 24: 905-919.
Direct Link  |  

3:  Espinosa-Duro, V., 2003. Fingerprints thinning algorithm. Aerospace and electronic systems magazine. IEEE., 18: 28-30.

4:  Hatano, T., T. Adachi, S. Shigematsu, H. Morimura, S. Onishi, Y. Okazaki and H. Kyuragi, 2002. A fingerprint verification algorithm using the differential matching rate. Proceedings of the International Confedence Pattern Recognization, August 11-15, 2002, IEEE Computer Society Press, pp: 799-802.

5:  Hong, L., Y. Wan and A. Jain, 1998. Fingerprint image enhancement: Algorithm and performance evaluation. IEEE Trans. Pattern Anal. Mach. Intell., 20: 777-789.
CrossRef  |  Direct Link  |  

6:  Jain, A., L. Hong and R. Bolle, 1997. On-line fingerprint verification. IEEE Trans. Pattern Anal. Mach. Intell., 19: 302-314.
CrossRef  |  

7:  Jain, A.K., S. Prabhakar, L. Hong and S. Pankanti, 2000. Filterbank-based fingerprint matching. Image Process., 9: 846-859.
Direct Link  |  

8:  Jain, A.K., A. Ross and S. Prabhakar, 2004. An introduction to biometric recognition. IEEE Trans. Circuits Syst. Video Technol., 14: 4-20.
CrossRef  |  Direct Link  |  

9:  Liao, P.S., T.S. Chen and P.C. Chung, 2001. A fast algorithm for multilevel thresholding. J. Inform. Sci. Eng., 17: 713-727.
Direct Link  |  

10:  Maltoni, D., D. Maio, A.K. Jain and S. Prabhakar, 2003. Handbook of Fingerprint Recognition. 2nd Edn., Springer, New York, USA., Pages: 348..

11:  Mehtre, B.M. and B. Chatterjee, 1989. Segmentation of fingerprint images. A composite method. Pattern Recog., 22: 381-385.

12:  Patil, P.M., S.R. Suralkar and H.K. Abhyankar, 2005. Fingerprint verification based on fixed length square finger code. Proceedings of the 17th International Conference on Tools with Artificial Intelligence, November 14-16, 2005, IEEE Computer Society Press, pp: 662-.

13:  Rusyn, B., V. Ostap and O. Ostap, 2002. A correlation method for fingerprint image recognition using spectral features. Modern Problems Radio Eng. Telecommun. Comput. Sci., 18-23: 219-220.
Direct Link  |  

14:  Shi, Z. and V. Govindaraju, 2006. A chaincode based scheme for fingerprint feature extraction. Pattern Recog. Lett., 27: 462-468.
CrossRef  |  

15:  Tico, M. and P. Kuosmanen, 2000. An algorithm for fingerprint image postprocessing, signals, systems and computers. Asilomar Conf., 2: 1735-1739.

16:  Wang, S. and Y. Wang, 2004. Fingerprint enhancement in the singular point area. Signal Process. Lett. IEEE., 11: 16-19.

©  2021 Science Alert. All Rights Reserved