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
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,
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:
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:
||Regions of integration of the sine components and detected
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
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:
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.
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, stands
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
||Driving the feature vectors of the normalized template and
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.
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.
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.
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.
||Good quality template and input FI (first row) and their corresponding
selected signatures and cross correlations (second row)
|| Execution times of matching algorithm (on P4 2.8 MHz PC with
512 MB RAM and WinXP OS, FVC2000 Db1_a)
||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
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.