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.
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Şo
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:
| (1) |
| (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:
| (3) |
| (4) |
| (5) |
| 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:
| (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.
| (7) |
| (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,
| 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.
| (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.
| (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.
| (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.
| 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) |
| 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.